Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int V;
- vector<vector<int>> edges, sccs;
- vector<bool> visited;
- stack<int> S;
- void post_order(int u)
- {
- if (!visited[u])
- {
- visited[u] = true;
- for (int v : edges[u])
- post_order(v);
- S.push(u);
- }
- }
- void Kosaraju()
- {
- vector<vector<int>> rev_edges(V);
- visited.assign(V, false);
- for (int u = 0; u < V; u++)
- {
- post_order(u);
- for (int v : edges[u])
- rev_edges[v].push_back(u);
- }
- visited.assign(V, false);
- while (!S.empty())
- {
- int src = S.top(); S.pop();
- if (!visited[src])
- {
- queue<int> Q({ src });
- visited[src] = true;
- sccs.push_back({});
- while (!Q.empty())
- {
- int u = Q.front(); Q.pop();
- sccs.back().push_back(u);
- for (int v : rev_edges[u])
- if (!visited[v])
- Q.push(v), visited[v] = true;
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement