blob: aa73486032f9ccaae0f4f9ddea2b5cf67db149f8 (
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
|
// Laufzeit: O(|V|+|E|)
vector< vector<int> > adjlist;
vector<bool> isArt;
vector<int> d, low;
int counter, root; // root >= 2 <=> Wurzel Artikulationspunkt
vector<ii> bridges; // Nur fuer Brücken.
void dfs(int v, int parent) { // Mit parent=-1 aufrufen.
d[v] = low[v] = counter++;
if (parent == 0) root++;
for (auto w : adjlist[v]) {
if (!d[w]) {
dfs(w, v);
if (low[w] >= d[v]) isArt[v] = true;
if (low[w] > d[v]) bridges.push_back(ii(v, w));
low[v] = min(low[v], low[w]);
} else if (w != parent) {
low[v] = min(low[v], d[w]);
}}}
void findArticulationPoints() {
counter = 1; // Nicht auf 0 setzen!
low.resize(adjlist.size());
d.assign(adjlist.size(), 0);
isArtPoint.assign(adjlist.size(), false);
bridges.clear(); //nur fuer Bruecken
for (int v = 0; v < (int)adjlist.size(); v++) if (!d[v]) dfs(v, -1);
}
|
