Kosaraju

发表于 更新于 分类于 本文字数： 249 阅读时长 ≈ 1 分钟

在计算科学中，Kosaraju的算法（又称为–Sharir Kosaraju算法）是一个线性时间(linear time)算法找到的有向图的强连通分量。它利用了一个事实，逆图（与各边方向相同的图形反转, transpose graph）有相同的强连通分量的原始图。

首先第一遍dfs扫一遍得到逆后序压倒栈dfn中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int vis[MAX];
vector<int> dfn;
f(i, 1, n){
        if (!vis[i])
            dfs(i);
    }
void dfs(int x)
{
    vis[x] = 1;
    for (auto it : rim[x])//rim[x]这个vector中储存x连向其他点的边
    {
        if (!vis[it])
            dfs(it);
    }
    dfn.pb(x);
}

然后FILO进行第二次dfs扫逆图，对于每次递归结束的点集构成一个强连通分量

要注意的是标记的mark不能为0，否则这处if (!mark[*it])会出错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int cnt;
void dfs1(int x)
{
    mark[x] = cnt, t[cnt] += a[x];
    //cout<<a[x]<<"jkj\n";
    for (auto it : nrim[x])
    {
        if (!mark[it])
            dfs1(it);
    }
}
for (auto it = dfn.rbegin(); it != dfn.rend(); it++)
    {
        if (!mark[*it])
        {
            cnt+=1;
            dfs1(*it);
        }
    }