Advertisement
shek_shek

temp

Jul 5th, 2015
261
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.52 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stack>
  3. #include <math.h>
  4. #include <time.h>
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <string>
  8. #include <set>
  9. #include <iomanip>
  10. #include <vector>
  11. #include <map>
  12. #include <cassert>
  13. #include <queue>
  14. #include <fstream>
  15.  
  16. using namespace std;
  17.  
  18. typedef long long li;
  19. typedef long double ld;
  20.  
  21. #define forn(i, n) for (int i = 0; i < int(n); ++i)
  22. #define pb push_back
  23. #define mp make_pair
  24. #define all(v) v.begin(),v.end()
  25. #define EPS 1e-9
  26. #define PI 3.1415926535897932384626433832795
  27.  
  28. const int MAXN = 20000;
  29.  
  30. vector <int> g[MAXN];
  31. bool used[MAXN];
  32. int depth[MAXN], fup[MAXN];
  33. vector <int> ans;
  34.  
  35. void dfs (int v, int p = -1) {
  36.     used[v] = true;
  37.     fup[v] = depth[v];
  38.     int children = 0;
  39.     for (int i = 0; i < g[v].size(); i++) {
  40.         int to = g[v][i];
  41.         if (to == p)  
  42.             continue;
  43.         if (used[to])
  44.             fup[v] = min (fup[v], depth[to]);
  45.         else {
  46.             depth[to] = depth[v] + 1;
  47.             dfs (to, v);
  48.             fup[v] = min (fup[v], fup[to]);
  49.             if (fup[to] >= depth[v] && p != -1)
  50.                 ans.push_back(v);
  51.             children++;
  52.         }
  53.     }
  54.     if (p == -1 && children > 1)
  55.         ans.push_back(v);
  56. }
  57.  
  58. int main () {
  59. #ifdef _DEBUG
  60.     freopen("input.txt", "r", stdin);
  61.     //freopen("output.txt", "w", stdout);
  62. #endif
  63.     int n, m;
  64.     cin >> n >> m;
  65.     forn (i, m) {
  66.         int a, b;
  67.         cin >> a >> b;
  68.         a--, b--;
  69.         g[a].push_back(b);
  70.         g[b].push_back(a);
  71.     }
  72.     for (int i = 0; i < n; i++) {
  73.         if (!used[i])
  74.             dfs(i);
  75.     }
  76.     cout << ans.size() << endl;
  77.     sort(all(ans));
  78.     forn (i, ans.size())
  79.         cout << ans[i] + 1 << endl;
  80.  
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement