边的分类

这里先讨论关于边的几种分类，参考《算法导论》给出的定义。

  1. 树边：如果结点 vv 是因算法对边 (u,v)(u,v) 的探索而首先被发现，则 (u,v)(u, v) 是一条树边。
  2. 前向边：将结点 uu 连接到其在 DFS 树中一个后代结点 vv 的边 (u,v)(u,v)，树边就是一种特殊的前向边。
  3. 后向边：将结点 uu 链接到其在 DFS 树中一个祖先结点 vv 的边 (u,v)(u,v)。
  4. 横向边：或者横插边，指其他所有的边。这些边可以连接同一棵 DFS 树中的结点，只要其中一个结点不是另外一个结点的祖先，也可以连接不同 DFS 树中的两个结点。

对于无向图，不存在横向边，如果存在横向边 (u,v)(u,v) 那么 uu 会在搜索 vv 的时候被搜到，这时 (v,u)(v,u) 就是一个简单的树边，至于后面也就是后向边，而不是横向边了。

强连通分量

给定一个 n 个点 m 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

题目链接：P3387。

一个有向图中，强连通分量（Strongly Connected Component）内的任意两点 u,vu,v 都是可以互相到达的，也就是存在环。用 Tarjan 算法可以在线性的时间内找到有向图中的所有强连通分量。

将这些强连通分量缩为点，就得到了一个 DAG，因为没有了环的存在，就可以很方便求解一些问题了。

Tarjan 算法的流程大致如下：

  1. 对于每个点 uu，都有 dfn(u),low(u)dfn(u), low(u) 分别表示当前点被遍历到的时间戳，和它能到达的最小时间戳，初始化时它们相同。

  2. 将 uu 入栈。

  3. 遍历 uu 的所有相邻结点 vv：

    • 如果 vv 没被遍历过，就遍历 vv，将 low(u)=min⁡{low(u),low(j)}low(u)=\min\{low(u), low(j)\}

    • 如果 vv 遍历过了并且在栈中（如果不在意味着 vv 属于别的强连通分量），将 low(u)=min⁡{low(u),dfn(j)}low(u)=\min \{low(u), dfn(j)\}

      虽然我这里写了 low(u)=min⁡{low(u),low(j)}low(u)=\min\{low(u), low(j)\} 虽然也是能 AC，而且经过检验每组测试数据 low(j)low(j) 对应的结点也确实在栈中，但是这和算法的逻辑不相同，因此还是写 dfn(j)dfn(j) 较好。

  4. 如果遍历完所有结点后 dfn(u)=low(u)dfn(u)=low(u) 仍然成立，就说明 uu 是其所在强连通分量中时间戳最小的点，弹出栈中元素直到 uu 为止都是其所在强连通分量中的结点。

  5. 值得说明的是，如果一个点不在任何环中，它本身也是一个强连通分量。

在一个 DAG 中 DFS 序搜到的所有点，考虑下面的伪代码：

1
2
3
4
5
def dfs(u):
    lst = []
    for j in u.next:
        dfs(j)
        lst.append(j)

最终在 lst 中的所有结点一定是按照拓扑序倒序排列的，所以用 Tarjan 搜到的所有强连通分量的编号顺序与拓扑序相反。

将图用 Tarjan 缩点后，将点权看做入边的边权，对 DAG 求一个最值即可。

在上面也说过，编号的倒序就是拓扑序的正序，然后再注意可能存在孤立的强连通分量，每个点的路径起码要和自己的权取一个最大值。

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
#include <stack>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 20010, M = 200010;
int h[N], sh[N], e[M], ne[M], p[N], idx;
int dfn[N], low[N], id[N], w[N], dist[N], timestamp, cntscc;
stack<int> stk;
bool instk[N];
int n, m;

void add(int h[], int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);
    instk[u] = true;

    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) tarjan(j), low[u] = min(low[u], low[j]);
        else if (instk[j]) low[u] = min(low[u], dfn[j]);
    }

    if (low[u] == dfn[u]) {
        int y;
        ++cntscc;
        do {
            y = stk.top(); stk.pop();
            id[y] = cntscc;
            w[cntscc] += p[y];
            instk[y] = false;
        } while (y != u);
    }
}

int main() {
    memset(h, -1, sizeof h);
    memset(sh, -1, sizeof sh);

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
    for (int i = 1, a, b; i <= m; i++) scanf("%d%d", &a, &b), add(h, a, b);

    for (int u = 1; u <= n; u++)
        if (!dfn[u]) tarjan(u);

    for (int u = 1; u <= n; u++) {
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (id[u] != id[j]) add(sh, id[u], id[j]);
        }
    }
    
    int res = 0;
    for (int u = cntscc; u; u--) {
        dist[u] = max(dist[u], w[u]);
        for (int i = sh[u]; ~i; i = ne[i]) {
            int j = e[i];
            dist[j] = max(dist[j], dist[u] + w[j]);
        }
        res = max(res, dist[u]);
    }

    return !printf("%d\n", res);
}

割点

给出一个 nn 个点，mm 条边的无向图，求图的割点。

输入格式

第一行输入两个正整数 n,mn,m。

下面 mm 行每行输入两个正整数 x,yx,y 表示 xx 到 yy 有一条边。

输出格式

第一行输出割点个数。

第二行按照节点编号从小到大输出节点，用空格隔开。

对于全部数据，1≤n≤2×1041\leq n \le 2\times 10^4，1≤m≤1×1051\leq m \le 1 \times 10^5。

题目链接：P3388。

对于边 (x,y)(x,y) 如果 xx 为割点，那么需要满足：

  • 当 xx 不是根节点时，low(y)≥dfn(x)low(y)\ge dfn(x) 表明 yy 无论如何也无法搜到比 xx 更早的结点。
  • 当 xx 为根节点时，至少有两个子结点满足 low(yi)≥dfn(x)low(y_i) \ge dfn(x)，那么 xx 就是割点。
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
#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 20010, M = 210000;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int n, m;
set<int> cut;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u, int from) {
    dfn[u] = low[u] = ++timestamp;
    // 当前节点连接的点双数量
    int sons = 0;

    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if (low[j] >= dfn[u]) {
                sons++;
                if (from != -1) cut.insert(u); 
            }
        }
        else low[u] = min(low[u], dfn[j]);
    }

    if (sons >= 2 && from == -1) cut.insert(u);
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);

    for (int i = 1, a, b; i <= m; i++)
        scanf("%d%d", &a, &b), add(a, b), add(b, a);

    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i, -1);

    printf("%d\n", (int)cut.size());
    for (int v: cut) printf("%d ", v);
    return puts(""), 0;
}

点双连通分量

对于一个 nn 个节点 mm 条无向边的图，请输出其点双连通分量的个数，并且输出每个点双连通分量。

输入格式

第一行，两个整数 nn 和 mm。

接下来 mm 行，每行两个整数 u,vu, v，表示一条无向边。

输出格式

第一行一个整数 xx 表示点双连通分量的个数。

接下来的 xx 行，每行第一个数 aa 表示该分量结点个数，然后 aa 个数，描述一个点双连通分量。

你可以以任意顺序输出点双连通分量与点双连通分量内的结点。

对于 100%100\% 的数据，1≤n≤5×1051 \le n \le 5 \times10 ^5，1≤m≤2×1061 \le m \le 2 \times 10^6。

题目链接：P8435。

定义

极大的，不包含割点（删掉点和它的所有邻边后整个图不连通）的连通块。注意，这里的割点对应的是整个图，而在一个子图内部它并不是割点。

性质

点双连通分量中的任意两点都在至少一个简单环中，等价于两点间存在两条不相交（无公共点）的路径。

必要性：无论删掉哪个点两点都可以互达，因此图中不存在割点，必要性得证。

充分性：反证，假设存在两点 u,vu,v 不同时处于一简单环中，如果两点间只有一条路径，必然存在割点；如果有大于等于两条路径，若这些路径不相交于 u,vu,v 以外的点就必定成环，所以这些路径一定交于某点，这个点也就成为了割点，就不是点双连通分量，推出矛盾，充分性得证。

注意，两个点一条边构成的无向图和孤立点也是符合定义的，它们是特例。

算法

  1. 对于每个点 uu 都使 dfn(u)=low(u)dfn(u)=low(u)，为其分配一个时间戳。

  2. 将 uu 入栈。

  3. 遍历 uu 的所有相邻结点 vv，不包含其 DFS 树中的父结点：

    • 如果没有遍历过就 DFS 遍历，然后 low(u)=min⁡{low(u),low(v)}low(u)=\min\{low(u), low(v)\}

      遍历之后判断 uu 点是否为割点，如果是那就弹栈弹到 vv 为止，再把 uu 加进当前点双连通分量中。

    • 否则 low(u)=min{low(u),dfn(v)}low(u)=min\{low(u), dfn(v)\}

  4. 如果 dfn(u)=low(u)dfn(u) = low(u)，说明 uu 是在它所在的双连通分量中时间戳最小的一个点，那么将栈中到它之前所有元素都加入一个双连通分量中。

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
#include <vector>
#include <stack>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 500010, M = 4000010;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp, cntvdcc;
stack<int> stk;
vector<int> vdcc[N];
int n, m;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u, int fa) {
    int sons = 0;
    stk.push(u);
    dfn[u] = low[u] = ++timestamp;

    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j, u);
            low[u] = min(low[u], low[j]);

            // 虽然 u 可能不是割点, 但不影响它在一个点双中
            if (low[j] >= dfn[u]) {
                sons++;
                vdcc[++cntvdcc].emplace_back(u);
                int y;
                do {
                    y = stk.top(); stk.pop();
                    vdcc[cntvdcc].emplace_back(y);
                } while (y != j);
            }
        }
        else low[u] = min(low[u], dfn[j]);
    }

    // 孤立点也是点双
    if (fa == -1 && sons == 0) vdcc[++cntvdcc].emplace_back(u);
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);

    for (int i = 1, a, b; i <= m; i++) scanf("%d%d", &a, &b), add(a, b), add(b, a);
    
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) stack<int>().swap(stk), tarjan(i, -1);
    
    printf("%d\n", cntvdcc);
    for (int i = 1; i <= cntvdcc; i++) {
        printf("%d ", (int)vdcc[i].size());
        for (int v: vdcc[i]) printf("%d ", v);
        puts("");
    }

    return 0;
}

边双连通分量

对于一个 nn 个节点 mm 条无向边的图，请输出其边双连通分量的个数，并且输出每个边双连通分量。

输入格式

第一行，两个整数 nn 和 mm。

接下来 mm 行，每行两个整数 u,vu, v，表示一条无向边。

输出格式

第一行一个整数 xx 表示边双连通分量的个数。

接下来的 xx 行，每行第一个数 aa 表示该分量结点个数，然后 aa 个数，描述一个边双连通分量。

你可以以任意顺序输出边双连通分量与边双连通分量内的结点。

对于 100%100\% 的数据，1≤n≤5×1051 \le n \le 5 \times10 ^5，1≤m≤2×1061 \le m \le 2 \times 10^6。

题目链接：P8436。

定义

极大的，不包含桥边（如果这条边删掉之后整个图不连通）的连通块。

对于一个桥边 (x,y)(x, y) 满足 dfn(x)<low(y)dfn(x)\lt low(y)，也就是 yy 点能走到的最早的时间戳也晚于 xx 。

性质

边双连通分量中任意一条边都包含在至少一个简单环中。

必要性：如果该性质满足，删去任意一边都不影响环中两点之间的可达性，那么就一定是一个边双连通分量，必要性得证。

充分性：在一个边双连通分量中，反证：如果边 (u,v)(u,v) 不在一个简单环中，断掉该边后 u,vu, v 不可到达，充分性得证。

算法

  1. 对于每个点 uu 都使 dfn(u)=low(u)dfn(u)=low(u)，为其分配一个时间戳。

  2. 将 uu 入栈。

  3. 遍历 uu 的所有相邻结点 vv，不包含其 DFS 树中的父结点：

    • 如果没有遍历过就 DFS 遍历，然后 low(u)=min⁡{low(u),low(v)}low(u)=\min\{low(u), low(v)\}

      如果满足 dfn(u)<low(v)dfn(u)\lt low(v) 那么当前边是一条桥边，标记一下。

    • 否则 low(u)=min{low(u),dfn(v)}low(u)=min\{low(u), dfn(v)\}

  4. 如果 dfn(u)=low(u)dfn(u) = low(u)，说明 uu 是在它所在的边双连通分量中时间戳最小的一个点，那么将栈中到它之前所有元素都加入一个双连通分量中。

这里 low(u)low(u) 的求法就和点双时的不一样了，点双中无所谓某个点是否能到达父结点的，而边双需要用这个判断，如果有重边的话这些边都不可能是桥边，所以传给 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
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stack>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 500010, M = 4000010;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp, cntedcc;
int n, m;
stack<int> stk;
vector<int> edcc[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u, int from) {
    stk.push(u);
    dfn[u] = low[u] = ++timestamp;

    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];

        if (!dfn[j]) tarjan(j, i), low[u] = min(low[u], low[j]);
        else if (i != (from ^ 1)) low[u] = min(low[u], dfn[j]);
    }

    if (low[u] == dfn[u]) {
        ++cntedcc;
        int y;
        do {
            y = stk.top(); stk.pop();
            edcc[cntedcc].emplace_back(y);
        } while (y != u);
    }
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);

    for (int i = 1, a, b; i <= m; i++) scanf("%d%d", &a, &b), add(a, b), add(b, a);
    for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, -1);

    printf("%d\n", cntedcc);
    for (int i = 1; i <= cntedcc; i++) {
        printf("%d ", (int)edcc[i].size());
        for (int v: edcc[i]) printf("%d ", v);
        puts("");
    }

    return 0;
}

也可以处理出所有桥边然后对每个点搜一遍，不允许走桥边，这样每次搜到的就是在同一个边双内的点。

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
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int N = 500010, M = 4000010;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int n, m, cntedcc;
bool isbridge[M], st[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u, int from) {
    dfn[u] = low[u] = ++timestamp;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];

        if (!dfn[j]) {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if (low[j] > dfn[u]) isbridge[i] = isbridge[i^1] = true;
        }
        else if (i != (from ^ 1)) low[u] = min(low[u], dfn[j]);
    }

    if (low[u] == dfn[u]) cntedcc++;
}

void dfs(vector<int>& out, int u) {
    st[u] = true;
    out.emplace_back(u);
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (st[j] || isbridge[i]) continue;
        dfs(out, j);
    }
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);

    for (int i = 1, a, b; i <= m; i++) 
        scanf("%d%d", &a, &b), add(a, b), add(b, a);

    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i, -1);
    
    printf("%d\n", cntedcc);
    vector<int> edcc;
    for (int i = 1; i <= n; i++) {
        if (st[i]) continue;
        dfs(edcc, i);

        printf("%d ", (int)edcc.size());
        for (int v: edcc) printf("%d ", v);
        puts(""), edcc.clear();
    }

    return 0;
}