Advertisement
Josif_tepe

Untitled

Dec 12th, 2022
599
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.64 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <stack>
  5. using namespace std;
  6. const int maxn = 1e5 + 10;
  7. int n, m;
  8. vector<int> graph[maxn];
  9. int discoverable_time[maxn];
  10. int low_link[maxn];
  11. bool on_stack[maxn];
  12. int current_time = 0;
  13. void dfs(int node) {
  14.     discoverable_time[node] = current_time;
  15.     low_link[node] = current_time;
  16.     current_time++;
  17.     on_stack[node] = true;
  18.    
  19.     static stack<int> st;
  20.     st.push(node);
  21.    
  22.     for(int i = 0; i < (int) graph[node].size(); i++) {
  23.         int neighbour = graph[node][i];
  24.         if(discoverable_time[neighbour] == -1) {
  25.             dfs(neighbour);
  26.             low_link[node] = min(low_link[node], low_link[neighbour]);
  27.         }
  28.         else if(on_stack[neighbour]) {
  29.             low_link[node] = min(low_link[node], discoverable_time[neighbour]);
  30.         }
  31.     }
  32.     if(low_link[node] == discoverable_time[node]) {
  33.         while(!st.empty()) {
  34.             int t = st.top();
  35.             st.pop();
  36.             on_stack[t] = false;
  37.             cout << t + 1 << " ";
  38.             if(t == node) {
  39.                 break;
  40.             }
  41.         }
  42.         cout << endl;
  43.     }
  44. }
  45. void tarjanSCC() {
  46.     for(int i = 0; i < maxn; i++) {
  47.         discoverable_time[i] = -1;
  48.         on_stack[i] = false;
  49.         low_link[i] = -1;
  50.     }
  51.     for(int i = 0; i < n; i++) {
  52.         if(discoverable_time[i] == -1) {
  53.             dfs(i);
  54.         }
  55.     }
  56. }
  57. int main()
  58. {
  59.     cin >> n >> m;
  60.    
  61.     for(int i = 0; i < m; i++) {
  62.         int a, b;
  63.         cin >> a >> b;
  64.         a--; b--;
  65.         graph[a].push_back(b);
  66.     }
  67.     tarjanSCC();
  68.     return 0;
  69. }
  70.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement