Advertisement
tien_noob

strong connects

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