blob: f2883efd3dfba481575b5c19f036b3ded24fe6b1 (
plain)
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
|
// Laufzeit: O(|V|+|E|)
int counter, sccCounter;
vector<bool> visited, inStack;
vector< vector<int> > adjlist;
vector<int> d, low, sccs;
stack<int> s;
void visit(int v) {
visited[v] = true;
d[v] = counter; low[v] = counter; counter++;
inStack[v] = true; s.push(v);
for (int i = 0; i < (int)adjlist[v].size(); i++) {
int u = adjlist[v][i];
if (!visited[u]) {
visit(u);
low[v] = min(low[v], low[u]);
} else if (inStack[u]) {
low[v] = min(low[v], low[u]);
}
}
if (d[v] == low[v]) {
int u;
do {
u = s.top(); s.pop(); inStack[u] = false;
sccs[u] = sccCounter;
} while(u != v);
sccCounter++;
}
}
void scc() {
// Initialisiere adjlist!
visited.clear(); visited.assign(NUM_VERTICES, false);
d.clear(); d.resize(NUM_VERTICES);
low.clear(); low.resize(NUM_VERTICES);
inStack.clear(); inStack.assign(NUM_VERTICES, false);
sccs.clear(); sccs.resize(NUM_VERTICES);
counter = 0;
sccCounter = 0;
for (i = 0; i < NUM_VERTICES; i++) {
if (!visited[i]) {
visit(i);
}
}
// sccCounter ist Anzahl der starkem Zusammenhangskomponenten.
// sccs enthält den Index der SCC für jeden Knoten.
}
|
