Advertisement
Guest User

Untitled

a guest
Oct 16th, 2018
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.55 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int n, m, t;
  8. vector <vector <int>> G;
  9. vector <int> enter;
  10. vector <int> back;
  11. vector <bool> visited;
  12. vector <int> node;
  13.  
  14. void dfs(int u, int p = 0){
  15.     visited[u] = true;
  16.     enter[u] = back[u] = t++;
  17.     int c = 1;
  18.     for (int i = 0; i < G[u].size(); i++){
  19.         int v = G[u][i];
  20.         if (v == p){
  21.             continue;
  22.         }
  23.         if (visited[v]){
  24.             back[u] = min(back[u], enter[v]);
  25.         } else {
  26.             dfs(v, u);
  27.             back[u] = min(back[u], back[v]);
  28.             if ((back[v] >= enter[u]) && (p != 0)){
  29.                 node.push_back(u);
  30.             }
  31.             ++c;
  32.         }
  33.     }
  34.     if ((p == 0) && (c > 2)){
  35.         node.push_back(u);
  36.     }
  37. }
  38.  
  39. int main() {
  40.     int dep, dest;
  41.     cin >> n >> m;
  42.  
  43.     G.resize(n+1);
  44.     back.resize(n+1);
  45.     enter.resize(n+1);
  46.     visited.resize(n+1);
  47.  
  48.     t = 0;
  49.  
  50.     for (int i = 1; i <= m; i++){
  51.         cin >> dep >> dest;
  52.         G[dep].push_back(dest);
  53.         G[dest].push_back(dep);
  54.     }
  55.  
  56.     for (int i = 0; i <= n; i++){
  57.         visited[i] = false;
  58.     }
  59.  
  60.     for (int i = 1; i <= n; i++){
  61.         if (!visited[i]) {
  62.             dfs(i);
  63.         }
  64.     }
  65.  
  66.     cout << node.size() << endl;
  67.  
  68.     sort(node.begin(), node.end());
  69.  
  70.     if (! node.empty()) {
  71.         cout << node[0] << " ";
  72.         for (int i = 1; i < node.size(); i++) {
  73.             if (node[i-1] != node[i])
  74.                 cout << node[i] << " ";
  75.         }
  76.     }
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement