时间戳

首页 > 技术文章 > 有向图强连通分量 Tarjan / 缩点

有向图强连通分量 Tarjan / 缩点

JHTBlog 2020-08-30 22:12 原文

1.有向图强连通分量

有向图G中一个两两顶点能互相到达的子图是G的一个强连通子图

一个无法拓展的强连通子图是原图的一个强连通分量（极大强连通子图），一个有向图G有多个强连通分量

2. \(Tarjan\ O(N + M)\)求强连通分量

Tarjan算法基于深度优先遍历。

在一棵DFS树里，定义：

  • 树边，DFS树上的边

  • 前向边，指向子孙的边

  • 后向边，指向祖先的边

  • 横叉边，指向其它子树的边

我们关心后向边和横叉边，他们可能构成强连通子图；

用 \(dfn[i]\) 记录节点 \(i\) 的入栈时间，\(low[i]\) 记录节点 \(i\) 能到达的入栈时间最早的节点，\(co[i]\) 表示节点 \(i\) 所在的强连通分量的序号。

我们发现当 \(dfn[i] = low[i]\) 时，节点 \(i\) 无法到达其祖先，所以 \(i\) 所在的强连通分量在子树 \(i\) 中；

我们在栈中保留没有确定其所在强连通分量的节点，那么 \(i\) 所在的强连通分量为栈顶到 \(i\) 的所有节点，所以我们更新这些节点的 \(co\) 并将它们出栈。

这个过程是递归进行的所以栈中的节点一定没有确定其强连通分量。

考虑怎么维护 \(low\) 数组，类似树形dp。

当从树边回溯时更新 \(low[x] = min(low[x], low[to])\)

当连出的边为非树边，如果 $ !co[to]$ 更新 \(low[x] = min(low[x], low[to])\)

3. \(Tarjan\) 求有向图强连通分量代码

int tim;
int dfn[N], low[N], co[N], tot;
int stck[N], top;
void Tarjan(int x) {
    dfn[x] = low[x] = ++tim; // 时间戳
    stck[++top] = x; // 入栈
    for(int i = head[x]; i; i = edge[i].nxt) { // 遍历出边
        int to = edge[i].to;
        if(!dfn[to]) {
            Tarjan(to); // DFS
            low[x] = min(low[x], low[to]); // 更新low数组
        } else if(!co[to]) low[x] = min(low[x], low[to]);
    }
    if(dfn[x] == low[x]) { // 找到强连通分量
        co[x] = ++tot;
        while(stck[top] != x) { // 将栈顶到x记为一个强连通分量
            co[stck[top--]] = tot;
        }top--; // 把x弹掉
    }
    return ;
}

4.有向图缩点

有向图缩点就是把每个强连通分量缩成一个点，缩点后的图是一个有向无环图(DAG)。

模板题

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

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

直接缩点，在DAG里跑拓扑+DP。 \(f[to] = max(f[to], f[from] + b[to])\)

缩点实际上是新建一张图

缩点代码

#include <iostream>
#include <cstdio>
#include <queue>
#define N 10001
#define M 100001
using namespace std;

int n, m;
int a[N], b[N], ru[N]; // 原图点权和DAG点权

int head1[N], cnt1, head2[N], cnt2; // 开两张图
struct Edge {
    int to, nxt;
} edge1[M << 1], edge2[M << 1];
void Add1(int from, int to) {
    edge1[++cnt1].to = to, edge1[cnt1].nxt = head1[from];
    head1[from] = cnt1;
}
void Add2(int from, int to) {
    edge2[++cnt2].to = to, edge2[cnt2].nxt = head2[from];
    head2[from] = cnt2;
}

int tim;
int dfn[N], low[N], co[N], tot;
int stck[N], top;
void Tarjan(int x) {}

void Build() { // 缩点
    for(int u = 1; u <= n; ++u) // 遍历每条边
    for(int i = head1[u]; i; i = edge1[i].nxt) {
        int from = u, to = edge1[i].to;
        if(co[from] != co[to]) { // 不在同一强连通分量
            Add2(co[from], co[to]);
            ru[co[to]]++; // 入度
        }
    }
    for(int i = 1; i <= n; ++i) b[co[i]] += a[i]; // 更新点权
}

queue <int> q;
int f[N];
int Dp() { // 拓扑
    for(int i = 1; i <= tot; ++i) {
        if(!ru[i]) q.push(i);
        f[i] = b[i];
    }
    while(!q.empty()) {
	int k = q.front(); q.pop();
	for(int i = head2[k]; i; i = edge2[i].nxt) {
            int to = edge2[i].to;
            f[to] = max(f[to], f[k] + b[to]);
            ru[to]--;
            if(!ru[to]) q.push(to); // 入度为0加入队列
	}
    }
    int ans = -1e9;
    for(int i = 1; i <= tot; ++i)
	ans = max(ans, f[i]);
    return ans;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= m; ++i) { // 建图
        int x, y; scanf("%d%d", &x, &y);
        Add1(x, y);
    }
    for(int i = 1; i <= n; ++i)
        if(!dfn[i]) Tarjan(i); // 所有点都要被考虑到
    Build();
    printf("%d", Dp());
}

推荐阅读