用于图的缩点、求割点和桥。
Strongly Connected Component
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void tarjan (int u)
{
dfn[u] = low[u] = ++stmp;
vis[stk[++top] = u] = true;
for (int v : g[u])
if (!dfn[v])
tarjan(v), chkmin(low[u], low[v]);
else if (vis[v]) chkmin(low[u], dfn[v]);
if (dfn[u] ^ low[u]) return;
++cnt;
int v;
do vis[v = stk[top--]] = false;
while (v ^ u);
}
|
Double Connected Component
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
| 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;
}
|