Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int n;
- vector<vector<int>> adj;
- vector<vector<int>> adj_t;
- vector<bool> vis;
- vector<int> comp;
- vector<int> order;
- void visit(int u)
- {
- vis[u] = true;
- for(int v:adj[u]) if(!vis[v]) visit(v);
- order.push_back(u);
- }
- void assign(int u, int k)
- {
- comp[u] = k;
- for(int v:adj_t[u]) if(comp[v]==-1) assign(v, k);
- }
- void scc()
- {
- adj_t.resize(n);
- for(int u=0;u<n;u++) for(int v:adj[u]) adj_t[v].push_back(u);
- vis.resize(n);
- for(int u=0;u<n;u++) if(!vis[u]) visit(u);
- reverse(order.begin(), order.end());
- comp.assign(n, -1);
- int curr = 0;
- for(int u:order) if(comp[u]==-1) assign(u, curr++);
- }
- int main()
- {
- n = 7;
- adj = {
- {5,6},
- {0},
- {1,3,6},
- {4},
- {3},
- {0,4},
- {1,3}
- };
- scc();
- cout << "SCCs: ";
- for(int e:comp) cout << e << ' ';
- cout << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment