【图论】图的连通性问题合集

更新于 分类于 ， 阅读次数： 本文字数： 2.8k 阅读时长 ≈ 3 分钟

图连通性问题涉及到强连通分量、双连通、割点和桥的理解

强连通分量：Tarjan缩点

dfs时记录dfs序，入栈并标记，更新能访问到最早的dfs序

最早dfs序和当前dfs序相等则找到强连通分量

画图更好理解dfs序和最早dfs序的问题

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
struct Edge
{
    int from, to, nxt;
} edge[N], edge2[N];
int tot;
int head[N];
void add_edge(int u, int v)
{
    edge[++tot].to = v;
    edge[tot].from = u;
    edge[tot].nxt = head[u];
    head[u] = tot;
}
int tot2;
int head2[N];
int in[N];
void add_edge2(int u, int v)
{
    edge2[++tot2].to = v;
    edge2[tot2].from = u;
    edge2[tot2].nxt = head2[u];
    head2[u] = tot2;
    in[v]++;
}
int val[N]; //点权

int dfn[N], low[N]; //dfs序记录、追溯到的最早的栈中节点的次序号
int dfntot;         //dfs序
int st[N];          //栈
bool in_stack[N];   //是否入栈
int tp;             //栈顶指针
int scc[N], sc;     // 结点 i 所在 scc 的编号
int sz[N];          // 强连通 i 的大小
int scval[N];
void tarjan(int u)
{
    low[u] = dfn[u] = ++dfntot;    //记录dfs序
    st[++tp] = u, in_stack[u] = 1; //当前点入栈，并标记已入栈
    for (int i = head[u]; i; i = edge[i].nxt)
    {
        const int &v = edge[i].to;
        if (!dfn[v]) //没有访问过
        {
            tarjan(v);                    //递归访问
            low[u] = min(low[u], low[v]); //更新与u相连的连通图第一次访问的dfs序
        }
        else if (in_stack[v])             //成环
            low[u] = min(low[u], dfn[v]); //更新第一次访问的dfs序
    }
    if (dfn[u] == low[u]) //找到强连通分量
    {
        ++sc;
        while (st[tp] != u) //将环中的节点出栈并记录
        {
            scc[st[tp]] = sc;
            sz[sc]++;
            scval[sc] += val[st[tp]]; //强连通分量的权值
            in_stack[st[tp]] = 0;
            --tp;
        }
        scc[st[tp]] = sc; //上一次入栈的当前节点
        sz[sc]++;
        scval[sc] += val[st[tp]];
        in_stack[st[tp]] = 0; //出栈
        --tp;
    }
}
void rebuild() //缩点重构图
{
    for (int i = 1; i <= m; i++)
    {
        int scx = scc[edge[i].from], scy = scc[edge[i].to];
        if (scx == scy)
            continue; //强连通分量缩点了
        add_edge2(scx, scy);
    }
}
  • 注意：缩点之后重构图，可能会出现大量重边，有些题可能需要删除，尤其是拓扑路径计数的时候
  • 注：Tarjan使用了栈，求得的 SCC 编号相当于反拓扑序（2-SAT问题）

双连通

  • 无向图，删除任意一条边/一个点，仍是连通图，称边双连通/点双连通

  • 两个点是边双连通的，当且仅当它们的树上路径中不包含桥。

    • 从任意点dfs出一个生成树，于是有树边（黑+绿）和非树边（红）

    • 非树边覆盖的边（绿）和非树边，除此之外的（黑色边）一定是桥

  • 建一个新图，新图中的每一个点对应原图中的每一条树边（在上图中用蓝色点表示）。对于原图中的每一条非树边，将这条非树边对应的树上简单路径中的所有边在新图中对应的蓝点连成一个连通块（这在上图中也用蓝色的边体现出来了）。一个点不是割点，当且仅当与其相连的所有边在新图中对应的蓝点都属于同一个连通块。

割点：tarjan

注意：这里的low[i]和强连通分量中的定义不同，更新内容不同

初始dfs时from是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
int dfntot;
int dfn[N], low[N];
//low[u]表示,顶点u及其子树中的点，通过非dfs生成树边能够回溯到的最早的点dfn值
bool cut[N]; //是否为割点
void tarjan(int rt, int from)
{
    dfn[rt] = low[rt] = ++dfntot;
    int child = 0;
    for (auto it : G[rt])
    {
        if (it == from)
            continue;
        if (!dfn[it])
        {
            tarjan(it, rt);
            low[rt] = min(low[rt], low[it]);
            if (!from) //是根节点，只需判是否有两棵子树
                child++;
            else if (low[it] >= dfn[rt]) //不是根节点，且没有另一条路能绕回去
                cut[rt] = true;
        }
        low[rt] = min(low[rt], dfn[it]);
    }
    if (!from && child >= 2)
        cut[rt] = true;
}

桥

当isbridge[x]为真时，(father[x], x) 为一个桥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int dfntot;
int dfn[N], low[N];
//low[u]表示顶点u及其子树中的点，通过非dfs生成树边能够回溯到的最早的点dfn值
bool isbridge[N]; //是否为q
int fa[N];
void tarjan(int rt, int from)
{
    fa[rt]=from;
    dfn[rt] = low[rt] = ++dfntot;
    for (auto it : G[rt])
    {
        if (it == from)
            continue;
        if (!dfn[it])
        {
            tarjan(it, rt);
            low[rt] = min(low[rt], low[it]);
            if(low[it] > dfn[rt])
                isbridge[it] = true;
        }
        else if(dfn[it] < dfn[rt])
            low[rt] = min(low[rt], dfn[it]);
    }
}