简介

强连通分量(Strongly Connected Components)指有向图 GG 中的极大子图,其满足子图内所有顶点都可以互相到达。

强连通分量是有向图 GG 上的一种等价关系,每个 SCC 可以缩成一个点,便于后续的处理。

顺便吐槽一下最近在学校学的图论:把“连通分量”称为“连通分支”我忍了,把“二分图”称为“偶图”我也忍了,把“二叉树”叫“二元树”是什么鬼。虽然在图论学界术语不统一的背景下,对对象的称呼仅仅是习惯问题,但血压依然上来了((

模板题 | P3916 | 图的遍历

题目描述

给出 NN 个点, MM 条边的有向图,对于每个点 vv ,求 A(v)A(v) 表示从点 vv 出发,能到达的编号最大的点。

输入格式

11 行, 22 个整数 NN , MM 。 接下来 MM 行,每行 22 个整数 UiU_i , ViV_i ,表示边 (Ui,Vi)(U_i,V_i) 。点用 1,2,,N1, 2, \cdots , N 编号。

输出格式

NN 个整数 A(1),A(2),,A(N)A(1), A(2) , \cdots , A(N)

输入输出样例

输入

1
2
3
4
4 3
1 2
2 4
4 3

输出

1
4 4 3 4

说明/提示

说明/提示

  • 对于 60%60\% 的数据, 1N, M1031 \le N , \ M \le 10^3

  • 对于 100%100\% 的数据, 1N,M1051 \le N , M \le 10^5

Tarjan 算法

没错,又是 Tarjan 算法,不过不是求 LCA 的 Tarjan 算法。

DFS 生成树

scc1.png

顾名思义,对着图 GG 做 DFS 的时候生成的树。

此过程会生成几种可能的边:

  • 树边(tree edge):绿色边,每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
  • 反祖边(back edge):黄色边,也被叫做回边,即指向祖先结点的边。
  • 横叉边(cross edge):红色边,它主要是在搜索的时候遇到了一个已经访问过的结点,但是这个结点 并不是 当前结点的祖先时形成的。
  • 前向边(forward edge):蓝色边,它是在搜索的时候遇到子树中的结点的时候形成的。

求 SCC

主要维护两个变量:

  • dfn[u]表示 DFS 过程中u是第几个被遍历的节点。
  • low[u]表示以u为根的子树中,dfn值最小的节点,或通过返祖边、横叉边所能到达的dfn值最小的节点。

依据此思路,DFS 过程中的做法就很显然了,当搜索到节点u时,令其入栈,对于与u邻接的节点v

  • 如果v未被访问过,则vu的子节点,对v进行 DFS,回溯时令low[u] = min(low[u], low[v])
  • 如果v已被访问过,且在栈中,则令low[u]=min(low[u],dfn[v])
  • 如果v已被访问过,但不在栈中,说明这个节点的 SCC 信息已经被处理完了,不用管了。

解决方案

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
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1050;
int n, cc, tot, top, scc, st, end;
int head[maxn], dfn[maxn], low[maxn], stk[maxn], belong[maxn];
bool instk[maxn];
struct Node
{
int to, next, from;
} edge[maxn * maxn];
void addedge(int u, int v)
{
++cc;
edge[cc].from = u;
edge[cc].to = v;
edge[cc].next = head[u];
head[u] = cc;
}
void tarjan(int u)
{
low[u] = dfn[u] = ++tot;
stk[++top] = u;
instk[u] = true;
for (int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].to;
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (instk[v])
{
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u])
{
++scc;
int v;
do
{
v = stk[top--];
belong[v] = scc;
instk[v] = false;
} while (v != u);
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int to;
scanf("%d", &to);
while (to != 0)
{
addedge(i, to);
scanf("%d", &to);
}
}
for (int i = 1; i <= n; i++)
{
if (!dfn[i])
tarjan(i);
}
return 0;
}

请参见