-
Notifications
You must be signed in to change notification settings - Fork 0
/
tarjan.cpp
125 lines (110 loc) · 2.98 KB
/
tarjan.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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <stack>
#include <set>
#include "definitions.h"
int cur_num, num_scc;
vector<bool> visited, inStack;
vector<int> num, low, scc_num;
stack<int> s;
// If SCCs are contracted, this data structure
// contains the mapping from each SCC to its
// corresponding nodes.
Graph<Node> scc_to_node;
void initialize() {
cur_num = num_scc = 0;
visited.assign(n, false);
inStack.assign(n, false);
num.assign(n, 0);
low.assign(n, 0);
scc_num.assign(n, 0);
}
/**
* Simple Depth-First-Search extended with
* SCC calculation
*/
void visit(Node u) {
visited[u] = true;
num[u] = low[u] = cur_num++;
s.push(u);
inStack[u] = true;
FOREACH(g, u, v) {
if (!visited[v]) {
visit(v);
low[u] = min(low[u], low[v]);
} else if (inStack[v]) {
low[u] = min(low[u], low[v]);
}
}
if (num[u] == low[u]) {
Node v;
do {
v = s.top();
s.pop();
inStack[v] = false;
scc_num[v] = num_scc;
} while (u != v);
num_scc++;
}
}
/**
* Computes all strongly connected components of the input
* graph g. Afterwards, array scc_num contains the corresponding
* SCC number foreach node.
*/
void tarjan() {
initialize();
NODES(u, n) {
if (!visited[u]) {
visit(u);
}
}
}
/**
* Contracts the input graph by contracting all SCCs
* into a single node.
* Precondition: Call tarjan() before calling contractSCC()
*/
Graph<Node> contractSCC() {
// Using a temporary graph which contains a edge set
// foreach node to prevent duplication check during
// contraction
vector<set<Node>> tmp_g(num_scc, set<Node>());
scc_to_node.assign(num_scc, vector<Node>());
NODES(u, n) {
Node scc_u = scc_num[u];
scc_to_node[scc_u].push_back(u);
FOREACH(g, u, v) {
Node scc_v = scc_num[v];
// Ignore self loops
if (scc_u != scc_v) tmp_g[scc_u].insert(scc_v);
}
}
// Build graph data structure for contracted graph
Graph<Node> contraction(num_scc, vector<Node>());
NODES(u, num_scc) {
FOREACH(tmp_g, u, v) {
contraction[u].push_back(v);
}
}
return contraction;
}
// Use Implementation/Graph/input/4.in for example input
int main() {
// Read unweighted directed graph (1-indexed)
readGraph<false, false, true>();
printGraph<false, true>();
// Compute strongly connected components with Tarjan's algorithm
tarjan();
// Print strongly connected components
cout << "Number of strongly connected components: " << num_scc << endl;
cout << "Nodes to SCC: ";
NODES(u, n) {
cout << u << "(" << scc_num[u] << ") ";
}
cout << endl;
// Contract strongly connected components
Graph<Node> contraction = contractSCC();
cout << "Contracted Graph:" << endl;
printGraph<false>(contraction);
cout << "SCC to Nodes: " << endl;
printGraph<true>(scc_to_node);
}