tien_noob

Bridges and cut verticles

Feb 25th, 2021 (edited)
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.11 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <numeric>
  4. #include <set>
  5. #include <queue>
  6. #include <stack>
  7. #include <vector>
  8. #include <climits>
  9. #include <string>
  10. #include <cstdio>
  11. #include <cmath>
  12. #define task "TESTCODE"
  13. using namespace std;
  14. const int N = 1e5;
  15. vector<vector<int>> Adj;
  16. int n, m, x, y, Count = 0, Number[N+1], Low[N+1];
  17. bool CritNode[N+1];
  18. vector<int> criticalnodes;
  19. void read()
  20. {
  21.    cin >> n >> m;
  22.    Adj.resize(n+1);
  23.    while (m -- )
  24.    {
  25.        cin >> x >> y;
  26.        Adj[x].push_back(y);
  27.        Adj[y].push_back(x);
  28.    }
  29.    fill (CritNode, CritNode + n + 1, false);
  30. }
  31. void Visit (int u, int p)
  32. {
  33.     int Numchild = 0;
  34.     ++Count;
  35.     Low[u] = Number[u] = Count;
  36.     for (int v : Adj[u])
  37.     {
  38.         if (v != p)
  39.         {
  40.             if (Number[v] != 0)
  41.             {
  42.                 Low[u] = min(Low[u], Number[v]);
  43.             }
  44.             else
  45.             {
  46.                 Visit(v, u);
  47.                 ++Numchild;
  48.                 Low[u] = min(Low[u], Low[v]);
  49.                 if (u == p)
  50.                 {
  51.                     if (Numchild >= 2)
  52.                     {
  53.                         CritNode[u] = true;
  54.                     }
  55.                 }
  56.                 else
  57.                 {
  58.                     if (Low[v] >= Number[u])
  59.                     {
  60.                         CritNode[u] = true;
  61.                     }
  62.                 }
  63.                 if (Low[v] >= Number[v])
  64.                 {
  65.                     cout << u << ' '<< v << '\n';
  66.                 }
  67.             }
  68.         }
  69.     }
  70. }
  71. void solve()
  72. {
  73.    for (int i = 1; i <= n; ++ i)
  74.    {
  75.        if (Number[i] == 0)
  76.        {
  77.            Visit(i, i);
  78.        }
  79.    }
  80.    for (int i = 1; i <= n; ++ i)
  81.    {
  82.        if (CritNode[i])
  83.        {
  84.            criticalnodes.push_back(i);
  85.        }
  86.    }
  87.    cout << criticalnodes.size() << '\n';
  88.    for (int i : criticalnodes)
  89.    {
  90.        cout << i << ' ';
  91.    }
  92. }
  93. int main()
  94. {
  95.    ios_base::sync_with_stdio(false);
  96.    cin.tie(nullptr);
  97.    freopen(task".INP", "r", stdin);
  98.    //freopen(task".OUT", "w", stdout);
  99.    read();
  100.    solve();
  101. }
  102.  
Add Comment
Please, Sign In to add comment