用于图的缩点、求割点和桥。
Strongly Connected Component
查看代码
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
| void tarjan(int x)
{
dfn[x] = low[x] = ++stmp;
stk.push(x);
vis[x] = true;
for (int i = hd[x]; ~i; i = nxt[i])
if (!dfn[edg[i]])
{
tarjan(edg[i]);
low[x] = min(low[x], low[edg[i]]);
}
else if (vis[edg[i]])
low[x] = min(low[x], dfn[edg[i]]);
if (dfn[x] == low[x])
{
cnt++;
int y;
do
{
y = stk.top();
stk.pop();
vis[y] = false;
} while (y != x);
}
}
|
Double Connected Component
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
| void tarjan(int x, int fa)
{
dfn[x] = low[x] = ++stmp;
for (int i = hd[x]; ~i; i = nxt[i]) if (i ^ fa ^ 1)
if (!dfn[edg[i]])
{
tarjan(edg[i], i);
low[x] = min(low[x], low[edg[i]]);
if (dfn[x] < low[edg[i]]) bridge[i] = bridge[i ^ 1] = true;
}
else
low[x] = min(low[x], dfn[edg[i]]);
}
|
Vertex Double Connected Component
Check the root point specially.
因为判断可以取等，所以不必考虑来边。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void tarjan (int x, int rt)
{
dfn[x] = low[x] = ++stmp;
int cnt = 0;
for (int i : g[x])
if (!dfn[i])
{
++cnt;
tarjan(i, rt);
low[x] = min(low[x], low[i]);
if (low[i] >= dfn[x] && x ^ rt) cut[x] = true;
}
else low[x] = min(low[x], dfn[i]);
if (x == rt && cnt > 1) cut[x] = true;
}
|