forked from sukritishah15/DS-Algo-Point
-
Notifications
You must be signed in to change notification settings - Fork 0
/
StronglyConnectedComponents.cpp
65 lines (57 loc) · 1.06 KB
/
StronglyConnectedComponents.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
Strongly Connected Components
Author: Johnny Villegas
Github: Jvillegasd
*/
#include <bits/stdc++.h>
using namespace std;
int NUM_NODES = 100
vector<int> g[NUM_NODES], rg[NUM_NODES];
bool visited[NUM_NODES];
stack<int> s;
void DFS(int u) {
visited[u] = true;
for(auto v : g[u]) {
if (!visited[v]) {
DFS(v);
}
}
s.push(u);
}
void DFS_inv(int u) {
visited[u] = true;
print("Node: %d\n", u);
for(auto v : rg[u]) {
if (!visited[v]) {
DFS_inv(v);
}
}
}
void SCC() {
int comp = 1;
for (int u = 1; u <= NUM_NODES; u++) {
if (!visited[u]) {
DFS(u);
}
}
memset(visited, 0, sizeof(visited));
while(!s.empty()) {
int u = s.top();
s.pop();
if (visited[u]) {
continue;
}
printf("Component #%d:\n", comp++);
DFS_inv(u);
printf("\n");
}
}
int main() {
/*
This is the SCC Kosajaru algorithm. Before to run it, you have to
fill DAG "g" and its reverse "rg". Reverse DAG is the same DAG "g" but
edges are pointing to oppposite direction.
*/
SCC();
return 0;
}