专栏文章

题解：P3387 【模板】缩点

AAnhe
P3387题解参与者 6已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mip7bh5e
此快照首次捕获于
2025/12/03 07:20
3 个月前
此快照最后确认于
2025/12/03 07:20
3 个月前
查看原文

Kosaraju 算法与 Garbow 算法

发现大部分题解都是 tarjan 算法的题解，这里介绍两种其他的求强联通分量的算法，作为扩展思路。其时间复杂度与 tarjan 算法相同，都为 O(n+m)O(n+m)。

Kosaraju 算法

原理

该算法依靠两次简单的 DFS 实现：
第一次 DFS，选取任意顶点作为起点，遍历所有未访问过的顶点，并在回溯之前给顶点编号，也就是后序遍历。
第二次 DFS，对于反向后的图，以标号最大的顶点作为起点开始 DFS。这样遍历到的顶点集合就是一个强连通分量。对于所有未访问过的结点，选取标号最大的，重复上述过程。
两次 DFS 结束后，强连通分量就找出来了，Kosaraju 算法的时间复杂度为 O(n+m)O(n+m)。
上述的过程基于以下两个原理。
  • 一个有向图 GG，把 GG 所有的边反向，建立反图 rGrG，反图 rGrG 不会改变原图 GG 的强连通性。
  • 对原图 GG 和反图 rGrG 各做一次 DFS，可以确定强联通分量数量。
所以，在反图中，每次 DFS 都是从某强联通分量的一个点开始，且不会跳到其他强联通分量（这是因为被反向边阻断，可以自己手动模拟感性理解一下）。

代码（请原谅我的变量名命名习惯）

CPP
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int s=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
        f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=s*10+c-'0';
        c=getchar();
    }
    return s*f;
}
int n,m;
vector<int> a[1000007],ra[1000007],d[1000007],b[1000007];
int w[1000007],col[1000007],jss;
int rd[1000007],vv[1000007],dp[1000007];
bool vis[1000007];
vector<int> too;

void dfs1(int u) {
    vis[u] = 1;
    for(int v : a[u])
        if(!vis[v]) dfs1(v);
    too.push_back(u);
}

void dfs2(int u, int c) {
    col[u] = c;
    vv[c] += w[u];
    for(int v : ra[u])
        if(!col[v]) dfs2(v, c);
}

int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;++i)
        w[i]=read();
    
    for(int i=1;i<=m;++i){
        int u=read(),v=read();
        a[u].push_back(v);
        ra[v].push_back(u);
    }
    
    for(int i=1;i<=n;++i)
        if(!vis[i]) dfs1(i);
    reverse(too.begin(), too.end());
    
    for(int u : too)
        if(!col[u]) dfs2(u, ++jss);
    
    for(int u=1;u<=n;++u)
        for(int v : a[u])
            if(col[u] != col[v]) {
                b[col[u]].push_back(col[v]);
                rd[col[v]]++;
            }
    
    queue<int> q;
    for(int i=1;i<=jss;++i)
        if(!rd[i]) q.push(i);
    
    int ans = 0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        dp[u] += vv[u];
        ans = max(ans, dp[u]);
        
        for(int v : b[u]){
            dp[v] = max(dp[v], dp[u]);
            if(--rd[v] == 0) q.push(v);
        }
    }
    
    printf("%d\n", ans);
    return 0;
}
虽然 Kosaraju 算法与 Tarjan 算法的时间复杂度都为 O(n+m)O(n+m)，但 Kosaraju 算法需要进行两次 DFS，效率较劣于 Tarjan 算法。但 Kosaraju 算法实现简单，逻辑易懂（或许是吧...）。

Garbow 算法

建议先学习关于 Tarjan 算法的知识再对照学习该算法。

原理

Garbow 算法是 Tarjan 算法的另一种实现（但并不是优化），Tarjan 算法是用 dfndfn 和 lowlow 来计算强连通分量的根，Garbow 维护两个栈：主栈存储当前遍历路径的节点，临时栈辅助确定强连通分量的根节点。从节点 ww 开始的 DFS 过程中，当一条路径显示这组节点都属于同一个强连通分量时，只要栈顶节点的访问时间大于根节点 ww 的访问时间，就从第二个栈中弹出这个节点，那么最后只留下根节点 ww。在这个过程中每一个被弹出的节点都属于同一个强连通分量。
当回溯到某一个节点 ww 时，如果这个节点在第二个栈的顶部，就说明这个节点是强连通分量的起始节点，在这个节点之后搜索到的那些节点都属于同一个强连通分量，于是从第一个栈中弹出那些节点，构成强连通分量。

代码

CPP
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int s=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
        f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=s*10+c-'0';
        c=getchar();
    }
    return s*f;
}
int n,m;
vector<int> a[1000007],b[1000007];
int w[1000007],col[1000007],jss;
int rd[1000007],vv[1000007],dp[1000007];
int dfn[1000007],stk1[1000007],stk2[1000007],top1,top2,tot;

void garbow(int u) {
    dfn[u] = ++tot;
    stk1[++top1] = u;
    stk2[++top2] = u;
    for(int v : a[u]) {
        if(!dfn[v]) garbow(v);
        else if(!col[v])
            while(dfn[stk2[top2]] > dfn[v]) top2--;
    }
    if(stk2[top2] == u) {
        top2--;
        jss++;
        do {
            col[stk1[top1]] = jss;
            vv[jss] += w[stk1[top1]];
        } while(stk1[top1--] != u);
    }
}

int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;++i)
        w[i]=read();
    
    for(int i=1;i<=m;++i){
        int u=read(),v=read();
        a[u].push_back(v);
    }
    
    for(int i=1;i<=n;++i)
        if(!dfn[i]) garbow(i);
    
    for(int u=1;u<=n;++u)
        for(int v : a[u])
            if(col[u] != col[v]) {
                b[col[u]].push_back(col[v]);
                rd[col[v]]++;
            }
    
    queue<int> q;
    for(int i=1;i<=jss;++i)
        if(!rd[i]) q.push(i);
    
    int ans = 0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        dp[u] += vv[u];
        ans = max(ans, dp[u]);
        
        for(int v : b[u]){
            dp[v] = max(dp[v], dp[u]);
            if(--rd[v] == 0) q.push(v);
        }
    }
    
    printf("%d\n", ans);
    return 0;
}
注：以上部分内容参考OI Wiki。

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...