Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define MAX_N 20001
- #define ll long long int
- using namespace std;
- int n, m;
- struct Node {
- vector < int > adj;
- vector < int > rev_adj;
- };
- Node g[MAX_N];
- stack < int > S;
- bool visited[MAX_N];
- int component[MAX_N];
- vector < int > components[MAX_N];
- int numComponents;
- void dfs_1(int x) {
- visited[x] = true;
- for (int i = 0; i < g[x].adj.size(); i++) {
- if (!visited[g[x].adj[i]]) dfs_1(g[x].adj[i]);
- }
- S.push(x);
- }
- void dfs_2(int x) {
- printf("%d ", x);
- component[x] = numComponents;
- components[numComponents].push_back(x);
- visited[x] = true;
- for (int i = 0; i < g[x].rev_adj.size(); i++) {
- if (!visited[g[x].rev_adj[i]]) dfs_2(g[x].rev_adj[i]);
- }
- }
- void Kosaraju() {
- for (int i = 0; i < n; i++)
- if (!visited[i]) dfs_1(i);
- for (int i = 0; i < n; i++)
- visited[i] = false;
- while (!S.empty()) {
- int v = S.top();
- S.pop();
- if (!visited[v]) {
- printf("Component %d: ", numComponents);
- dfs_2(v);
- numComponents++;
- printf("\n");
- }
- }
- }
- int main() {
- cin >> n >> m;
- int a, b;
- while (m--) {
- cin >> a >> b;
- g[a].adj.push_back(b);
- g[b].rev_adj.push_back(a);
- }
- Kosaraju();
- printf("Total number of components: %d\n", numComponents);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement