Tarjan
割点、割边（桥）
对于无向连通图 $G=(V,E)$：
若对于 $x\in V$，从图中删去 $x$ 以及与其直接相连的点之后，$G$ 不再连通，则称 $x$ 为 $G$ 的割点。
若对于 $e\in E$，从图中删去 $e$ 后，$G$ 不再连通，则称 $e$ 为 $G$ 的割边或桥。
一般无向图（不一定连通）的割点和桥就是它的各个连通块的割点和桥。
Tarjan 求割边（桥）、割点
$low[x]$ 定义为搜索树中 $x$ 的子树以及经过一条非树边可以到达搜索树中 $x$ 的子树的节点的 $dfn[y]$ 的最小值。
注意
具体题中一定要注意图是否连通。
求割边（桥）
无向边 $(x,y)$ 是桥，当且仅当搜索树上 $y$ 是 $x$ 的子节点，且满足 $low[y]>dfn[x]$。
桥一定是搜索树中的边，一个简单环中的边一定都不是桥。割边必然在生成树中。
如果一个边不属于任何一个回路，那么它是一条割边。
利用此性质，可以求出任意一个生成树，然后向上加非树边，没有和任意一个非树边构成环的边就是割边，覆盖成环的操作可以使用树上差分，还可以使用树剖。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void tarjan(int x, int in_edge) {
ctb ++;
dfn[x] = low[x] = ctb;
for(int i = hd[x]; i; i = nxt[i]) {
int y = ver[i];
if(dfn[y] == 0) {
tarjan(y, i);
low[x] = min(low[x], low[y]);
if(low[y] > dfn[x])
bri[i] = bri[i ^ 1] = true;
} else if(i != (in_edge ^ 1))
low[x] = min(low[x], dfn[y]);
}
}
|
边 (S2OJ391)
给定一张图，判断其中的每条边在最小生成树中的情况：
1.不在任意一个最小生成树中，输出 none。
2.在部分最小生成树中，输出 at least one。
3.一定出现在最小生成树中，输出 any。
按照读入的顺序输出每条边的情况。
$n,m\le10^5$。
利用加边再断环的想法，用向上标记法，可以水过去（数据太水了，这种方法复杂度不对，会被卡到 $O(n^2)$）。
none 是好判断的，所以我们重点在于如何判断是 any 还是 at least one。
对于任意一个连通森林，连接两个连通块的权值最小的边一定在最小生成树中。但是如果有连接两个相同连通块的边权值相同，这两个边就会出现问题，从 any 变成了 at least one。
我们仔细思考上面的情况，可以发现问题出现在这种情况：有若干条权值相同的边，并且它们都可以连接两个不同的连通块。
那么，把连通块看成点，把这些权值相同的边加入，那么在这个图中的桥，都是 any，否则是 at least one。
那么我们跑一遍 $\rm Tarjan$，复杂度是 $O(边数)$ 的，所以总复杂度约 $O(m)$。
当然那时 $\rm Tarjan$ 的总复杂度，整个程序还有排序和并查集，是一个小常数 $O(n\log n)$。
这种将连通块看作点，以及多次判断是否为桥时的处理方法是很值得借鉴与思考的。
好题。
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
| #include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 100010;
struct Edge {
int rk, u, v, w;
};
struct Disjoint_Set {
int fa[N];
void djsinit(int x) {
for(int i = 1; i <= x; i ++)
fa[i] = i;
}
int Find(int x) {
return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
void Merge(int x, int y) {
x = Find(x);
y = Find(y);
fa[x] = y;
}
};
int n, m;
int ct = 1, hd[N], ver[N<<1], nxt[N<<1], rk[N<<1];
int ans[N];
Edge e[N];
Disjoint_Set djs;
vector<Edge> tmpe;
vector<int> tmpp;
bool cmp(Edge a, Edge b) {
return a.w < b.w;
}
void add(int u, int v, int rank) {
ver[++ct] = v;
rk[ct] = rank;
nxt[ct] = hd[u];
hd[u] = ct;
}
namespace Tarjan {
int ct, dfn[N], low[N];
int st;
void tarjan(int x, int ine) {
ct ++;
dfn[x] = low[x] = ct;
for(int i = hd[x]; i; i = nxt[i]) {
int y = ver[i];
if(dfn[y] == 0) {
tarjan(y, i);
low[x] = min(low[x], low[y]);
if(low[y] > dfn[x])
ans[rk[i]] = 2;
} else if(i != (ine ^ 1) && dfn[y] > st)
low[x] = min(low[x], dfn[y]);
}
}
void mian() {
st = ct;
int siz = tmpp.size();
for(int i = 0; i < siz; i ++)
dfn[tmpp[i]] = low[tmpp[i]] = 0;
for(int i = 0; i < siz; i ++)
if(dfn[tmpp[i]] == 0)
tarjan(tmpp[i], 0);
}
}
int main() {
scanf("%d%d", &n, &m);
e[m+1].w = -1;
for(int i = 1; i <= m; i ++) {
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
e[i].rk = i;
}
sort(e+1, e+m+1, cmp);
djs.djsinit(n);
for(int i = 1; i <= m;) {
int tmp = e[i].w;
while(e[i].w == tmp) {
int tx = djs.Find(e[i].u);
int ty = djs.Find(e[i].v);
if(tx == ty) {
i ++;
continue;
}
ans[e[i].rk] = 1;
Edge tmp2;
tmp2.rk = e[i].rk;
tmp2.u = tx;
tmp2.v = ty;
tmp2.w = e[i].w;
tmpe.push_back(tmp2);
i ++;
}
int siz = tmpe.size();
for(int j = 0; j < siz; j ++) {
Edge tmp3 = tmpe[j];
add(tmp3.u, tmp3.v, tmp3.rk);
add(tmp3.v, tmp3.u, tmp3.rk);
djs.Merge(tmp3.u, tmp3.v);
tmpp.push_back(tmp3.u);
tmpp.push_back(tmp3.v);
}
tmpe.clear();
Tarjan::mian();
tmpp.clear();
}
for(int i = 1; i <= m; i ++)
if(ans[i] == 0)
puts("none");
else if(ans[i] == 1)
puts("at least one");
else
puts("any");
return 0;
}
|
求割点
若 $x$ 是搜索树的根节点，则 $x$ 是割点当且仅当搜索树上存在至少两个子节点 $y_1,y_2$ 满足 $low[y_i]\ge dfn[x]$。
若 $x$ 不是搜索树的根节点，那么 $x$ 是割点当且仅当搜索树上存在一个 $x$ 的子节点 $y$ 满足 $low[y]\ge dfn[x]$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void tarjan(int x) {
ctb ++;
dfn[x] = low[x] = ctb;
int tmpcnt = 0;
for(int i = hd[x]; i; i = nxt[i]) {
int y = ver[i];
if(dfn[y] == 0) {
tarjan(y);
low[x] = std::min(low[x], low[y]);
if(low[y] >= dfn[x])
tmpcnt ++;
} else
low[x] = std::min(low[x], dfn[y]);
}
if((x != rt && tmpcnt == 1) || tmpcnt > 1)
cut[x] = true;
}
|
强连通分量（SCC）
定义在有向图上。
一张有向图，满足图中任意两个节点 $x,y$，都存在至少一条 $x$ 到 $y$ 的路径，那么是一张强连通图。
有向图的极大强连通子图称为“强连通分量”，简记为 SCC。
Tarjan 求强连通分量
注意
具体题中一定要注意图是否连通。
当然，其实连不连通都得从每个 $dfn[x]=0$ 的点搜一遍，因为有向图的连通比较难搞。
首先维护一个栈，包含 $x$ 的祖先节点和存在一条路径到达 $x$ 的祖先节点的点，那么如果从 $x$ 出发有一条边连接到了这些点，就可以形成环。
任意一个点或边都在至少一个简单环中。
定义为栈中的或者搜索树上 $x$ 的子树内有边连向 $x$ 的点的 $dfn[y]$ 的最小值。
进行 DFS，把搜索树上的点入栈，如果目标节点在栈中，则用 $dfn[y]$ 更新 $low[x]$，否则可以用 $low[y]$ 更新 $low[x]$。
不难发现，一个 SCC 中所有节点的 $low[x]$ 都等于 SCC 中最小的 $dfn[x]$，考虑让每个 SCC 是在它第一个被搜到的节点处统计，于是，我们在 $low[x]=dfn[x]$ 的点 $x$ 处统计，具体地，不断出栈，直至 $x$ 也出栈。
每个节点都包含在至少一个 SCC 中，因为实在不行它可以自己成一个 SCC，毕竟初始化 $low[x]=dfn[x]=cnt$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void tarjan(int x) {
ctb ++;
dfn[x] = low[x] = ctb;
stk[++top] = x;
ins[x] = true;
for(int i = hd[x]; i; i = nxt[i]) {
int y = ver[i];
if(dfn[y] == 0) {
tarjan(y);
low[x] = std::min(low[x], low[y]);
} else if(ins[y])
low[x] = std::min(low[x], dfn[y]);
}
if(low[x] == dfn[x]) {
ctc ++;
int y;
do {
y = stk[top--];
ins[y] = false;
bel[y] = ctc;
scc[ctc].push_back(y);
} while(x != y);
}
}
|
SCC 缩点
把 SCC 看作一个点，只把不在同一个 SCC 的边连上即可。