Advertisement
Guest User

175

a guest
Mar 22nd, 2018
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.51 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <string>
  5. #include <cstdio>
  6. #include <set>
  7. #include <map>
  8. #include <sstream>
  9. #include <iterator>
  10. #include <cmath>
  11. #include <unordered_map>
  12. #include <queue>
  13.  
  14. using namespace std;
  15.  
  16. void dfs(int u, int p, int dep, vector< vector<int> > &g,
  17.          vector<int> &d, vector<int> &fup, vector<int> &dots){
  18.     d[u] = fup[u] = dep;
  19.     int sons = 0;
  20.     bool isDot = false;
  21.     for (int i = 0; i < g[u].size(); ++i){
  22.         if(g[u][i] == p)
  23.             continue;
  24.         if(d[g[u][i]] >= 0)
  25.             fup[u] = min(fup[u], d[g[u][i]]);
  26.         else{
  27.             dfs(g[u][i], u, dep + 1, g, d, fup, dots);
  28.             fup[u] = min(fup[u], fup[g[u][i]]);
  29.             if(u != p && fup[g[u][i]] >= d[u])
  30.                 isDot = true;
  31.             sons++;
  32.         }
  33.     }
  34.     if(u == p && sons > 1)
  35.         isDot = true;
  36.  
  37.     if(isDot)
  38.         dots.push_back(u);
  39. }
  40.  
  41. int main(){
  42.     ios_base::sync_with_stdio(false);
  43.  
  44.     int n, m;
  45.     cin >> n >> m;
  46.     vector< vector<int> > g(n);
  47.     for (int i = 0; i < m; ++i){
  48.         int x, y;
  49.         cin >> x >> y;
  50.         g[x - 1].push_back(y - 1);
  51.         g[y - 1].push_back(x - 1);
  52.     }
  53.  
  54.     vector<int> d(n, -1);
  55.     vector<int> fup(n, -1);
  56.     vector<int> dots;
  57.     dfs(0, 0, 0, g, d, fup, dots);
  58.  
  59.     sort(dots.begin(), dots.end());
  60.  
  61.     cout << dots.size() << endl;
  62.     for (int i = 0; i < dots.size(); ++i)
  63.         cout << dots[i] + 1 << " ";
  64.  
  65.     cout << endl;
  66.     return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement