Advertisement
MinhNGUYEN2k4

Untitled

Aug 6th, 2020
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.10 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define pb(x) push_back(x)
  4. using namespace std;
  5. const int N = 100005;
  6.  
  7. int n,m,par[N],cnt=0;
  8. vector<int> a[N];
  9. vector<int> res;
  10. int num[N],low[N];
  11.  
  12. void dfs(int u)
  13. {
  14.     int x = (par[u] != -1);
  15.     num[u]=low[u]=++cnt;
  16.     for(int &v : a[u])
  17.     {
  18.         if (v == par[u]) continue;
  19.         if (par[v]) low[u] = min(low[u],num[v]);
  20.         else
  21.         {
  22.             par[v]=u;
  23.             dfs(v);
  24.             low[u]=min(low[u],low[v]);
  25.             if (low[v] >= num[u]) ++x;
  26.         }
  27.     }
  28.     if (x >= 2) res.pb(u);
  29. }
  30.  
  31. signed main()
  32. {
  33.     ios_base::sync_with_stdio(false);
  34.     cin.tie(0);cout.tie(0);
  35.     freopen("cnode.inp","r",stdin);
  36.     freopen("cnode.out","w",stdout);
  37.     cin >> n >> m;
  38.     for(int i=1; i<=m; ++i)
  39.     {
  40.         int u,v;
  41.         cin >> u >> v;
  42.         a[u].pb(v);
  43.         a[v].pb(u);
  44.     }
  45.     for(int i=1; i<=n; ++i)
  46.     {
  47.         if (!par[i])
  48.         {
  49.             par[i]=-1;
  50.             dfs(i);
  51.         }
  52.     }
  53.     cout << res.size() << endl;
  54.     for(int &i : res) cout << i << " ";
  55.     return 0;
  56. }
  57.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement