Advertisement
Korotkodul

Задача C. Points. Точки сочленения_WA_4

Oct 19th, 2021 (edited)
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. #include <vector>
  2. #include <algorithm>
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. vector <int> tin;
  7. vector <int> up;
  8. vector <bool> was;
  9. vector <vector<int>> gr;
  10. vector <bool> cut_p;
  11. int P = 0;
  12. void dfs(int v, int last, int timer) {
  13.     was[v] = true;
  14.     tin[v] = up[v] = timer;
  15.  
  16.     int child = 0;
  17.     for (int u: gr[v]){
  18.  
  19.         if (u == last) {
  20.  
  21.             continue;
  22.         }
  23.         else if (was[u] == true){
  24.  
  25.             up[v] = min(up[v], tin[u]);
  26.         }
  27.         else if (was[u] == false){
  28.             dfs(u, v, timer + 1);
  29.             up[v] = min(up[v], up[u]);
  30.             if (up[u] >= tin[v] && v != last){
  31.                 if (!cut_p[v]) P++;
  32.                 cut_p[v] = true;
  33.             }
  34.             child++;
  35.         }
  36.     }
  37.     if (v == last && child > 1) {
  38.         if (!cut_p[v]) P++;
  39.         cut_p[v] = true;
  40.     }
  41.  
  42. }
  43.  
  44.  
  45.  
  46. int main()
  47. {
  48.     int n, m;
  49.     cin >> n >> m;
  50.     gr.resize(n);
  51.     cut_p.resize(n, false);
  52.     for (int i = 0; i < m; ++i) {
  53.         int a, b;
  54.         cin >> a >> b;
  55.         a--;
  56.         b--;
  57.         gr[a].push_back(b);
  58.         gr[b].push_back(a);
  59.     }
  60.     tin.resize(n, -4);
  61.     up.resize(n, 1e9);
  62.     was.resize(n, false);
  63.  
  64.     dfs(0, 0, 0);
  65.  
  66.     cout << P<< '\n';
  67.     for (int i= 0;i<n;++i){
  68.         if (cut_p[i]){
  69.             cout<<i+1<<'\n';
  70.         }
  71.     }
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement