blob: b99a28687a177c4c1ad31352d9884f01673ea5f0 (
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
|
vector< vector<int> > adjlist;
vector<int> low;
vector<int> d;
vector<bool> isArtPoint;
vector< vector<int> > bridges; //nur fuer Bruecken
int counter = 0;
void visit(int v, int parent) {
d[v] = low[v] = ++counter;
int numVisits = 0, maxlow = 0;
for (vector<int>::iterator vit = adjlist[v].begin(); vit != adjlist[v].end(); vit++) {
if (d[*vit] == 0) {
numVisits++;
visit(*vit, v);
if (low[*vit] > maxlow) {
maxlow = low[*vit];
}
if (low[*vit] > d[v]) { //nur fuer Bruecken
bridges[v].push_back(*vit); bridges[*vit].push_back(v);
}
low[v] = min(low[v], low[*vit]);
} else {
if (d[*vit] < low[v]) {
low[v] = d[*vit];
}
}
}
if (parent == -1) {
if (numVisits > 1) isArtPoint[v] = true;
} else {
if (maxlow >= d[v]) isArtPoint[v] = true;
}
}
void findArticulationPoints() {
low.clear(); low.resize(adjlist.size());
d.clear(); d.assign(adjlist.size(), 0);
isArtPoint.clear(); isArtPoint.assign(adjlist.size(), false);
bridges.clear(); isBridge.resize(adjlist.size()); //nur fuer Bruecken
for (int v = 0; v < (int)adjlist.size(); v++) {
if (d[v] == 0) visit(v, -1);
}
}
|
