发现这部分学的最烂，稍微整理下。
强连通分量
定义
强连通的定义：有向图 G 强连通，当且仅当 G 的任意两个节点联通。
强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图。
Tarjan 算法
DFS 生成树
有向图的 DFS 生成树主要有 4 种边：
-
树边：是搜索时找到一个未访问的结点形成的边。
-
返祖边：是搜索时找到自己的祖先形成的边。
-
横叉边：是搜索时找到已遍历过的结点形成的边，并且这个节点不是自己的祖先和子树中的结点。
-
前向边：是搜索时找到子树中的结点形成的边。
DFS 生成树与强连通分量之前的关系
如果 u 是某个强连通分量在 DFS 生成树里搜到的第一个结点，这个强连通分量其它的结点一定在 u 的子树里。结点 u 被称为这个强连通分量的根。
证明：假设强连通分量其它的结点不都在 u 的子树里，那么不在的那些结点一定与 u 连有返祖边或者前向边，返祖边或者前向边相连的点都是遍历过的，所以该假设不成立。
Tarjan 算法求强连通分量
维护对于每个结点 u 维护两个值：
- dfnu 表示结点 u 是第几个被搜到的。
- lowu 表示在 u 的子树中能够回溯到的最早出现在栈中的结点。具体的，lowu 为以 u 为根的子树的和子树中通过一条不在搜索树上的边能到达的结点的 dfn 的最小值。
按照深度优先搜索依次搜索每个值，对于每个值维护 dfn 和 low。每找到一个强连通分量，就将这个强连通分量全部出栈（该强连通分量的所有元素都在栈顶）。在搜索过程中对于 u 与其相连的结点 v（v 不是 u 的父亲）：
- v 未被访问过：继续对 v 进行搜索，用 lowv 更新 lowu，因为 v 能够回溯到的点 u 一定也能回溯到。
- v 被访问过且在栈中：根据定义，用 dfnv 更新 lowu。
- v 被访问过且不在栈中：说明 v 已经被处理，不做更新。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| int dfn[N],low[N],idx;
int sta[N],top;
bool vis[N];
void tarjan(int u){
dfn[u] = low[u] = ++idx;
sta[++top] = u;
vis[u] = true;
for(auto v:g[u]){
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(vis[v])
low[u] = min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
do{
vis[sta[top]] = false;
}while(sta[top--]!=u);
}
}
|
割点和桥
定义
对于一张无向图，如果删去一个点后这张图的联通分量增加了，那么这个点是这张图的割点。
对于一张无向图，如果删去一条边后这张图的联通分量增加了，那么这条边是这张图的桥。
Tarjan 算法求割点
dfs 记录时间戳 low，同时记录每个结点不经过父亲能到达的结点最小的时间戳 low。
判断一个点 u 是割点的依据是存在儿子v 满足 lowv≤dfnu。因为如果 lowv≥dfnu，说明 v 一定有一条返祖边或者横叉边，删掉 u 之后 v 仍然与 u 的父亲联通，否则删到 u 之后 v 不连通，出现新的联通分量。
这个判定唯一不适用于 u 是根节点。因为根节点的儿子不可能与根节点的父亲联通（根节点没有父亲），所以如果根节点是割点，那么在 dfs 树中存在两个以上的儿子就一定是割点，删掉根结点后根结点的子树一定不连通。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| int dfn[N],low[N],idx;
vector<int> g[N];
bool vis[N];
void dfs(int u,int father){
dfn[u] = low[u] = ++idx;
int cnt = 0;
for(int v:g[u]){
if(!dfn[v]){
cnt++;
dfs(v,u);
low[u] = min(low[u],low[v]);
if(father&&dfn[u]<=low[v])
vis[u] = true;
}
else if(v!=father)
low[u] = min(low[u],dfn[v]);
}
if(!father&&cnt>1)
vis[u] = true;
}
|
Tarjan 算法求割边
和求割点差不多，不需要特殊处理根节点。
lowu 为不经过 u−v 这条边能到达的结点的最小时间戳。当 lowv>dfnu 时，u−v 这条边是割边。
因为 lowv=lowu 就证明 v 可以通过别的边到达 u。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int h[N],ne[M],e[M],idx;
int dfn[N],low[N],cnt;
bool vis[N];
void dfs(int u,int father){
dfn[u] = low[u] = ++cnt;
for(int k=h[u];~k;k=ne[k]){
int v = e[k];
if(!dfn[v]){
dfs(v,u);
low[u] = min(low[u],low[v]);
if(dfn[u]<low[v])
vis[k] = vis[k^1] = true;
}
else if(v!=father)
low[u] = min(low[u],dfn[v]);
}
}
|
双连通分量
定义
在一张无向图中，对于两个点 u,v，如果删去任意一条边都不能使其不连通，那么 u 和 v 是 边双连通 的。
在一张无向图中，对于两个点 u,v，如果删去任意一个点都不能使其不连通，那么 u 和 v 是 点双连通 的。
边双连通具有传递性，点双连通没有。
Tarjan 算法求点双连通
与边双连通不同，一个点可能属于多个点双连通分量。
除了独立点，所有点双连通都有两个以上的点构成。我们用栈维护点，当遇到割点或根节点时，将子树内目前不属于其它点双的非割点或在子树中的割点归到一个新的点双。注意这个点可能还是与其它点双的公共点，所以不能将其出栈。
代码实现
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
| vector<vector<int>> ans;
int dfn[N],low[N],idx;
vector<int> g[N];
int stk[N],tp;
void dfs(int u,int father){
dfn[u] = low[u] = ++idx;
if(g[u].empty()){
ans.push_back({u});
return;
}
stk[++tp] = u;
for(int v:g[u]){
if(!dfn[v]){
dfs(v,u);
low[u] = min(low[u],low[v]);
if(dfn[u]<=low[v]){
ans.push_back({});
do{
ans.back().push_back(stk[tp--]);
}while(stk[tp+1]!=v);
ans.back().push_back(u);
}
}
else if(v!=father)
low[u] = min(low[u],dfn[v]);
}
}
|
Tarjan 算法求边双连通
删掉割边所剩下的就是边双连通分量。割边用 Tarjan 求即可。
代码实现
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
| int h[N],ne[M],e[M],idx;
vector<vector<int>> ans;
int dfn[N],low[N],cnt;
bool b[M],vis[N];
int n,m;
void dfs(int u,int father){
dfn[u] = low[u] = ++cnt;
for(int k=h[u];~k;k=ne[k]){
int v = e[k];
if(!dfn[v]){
dfs(v,u);
low[u] = min(low[u],low[v]);
if(dfn[u]<low[v])
vis[k] = vis[k^1] = true;
}
else if(v!=father)
low[u] = min(low[u],dfn[v]);
}
}
void dfs(int u){
vis[u] = true;
ans.back().push_back(u);
for(int k=h[u];~k;k=ne[k]){
int v = e[k];
if(vis[v]||b[k])
continue;
dfs(v);
}
}
int main(){
for(int k=1;k<=n;k++)
if(!dfn[k])
dfs(k,0);
for(int k=1;k<=n;k++)
if(!vis[k]){
ans.push_back(vector<int>());
dfs(k);
}
}
|