算法详解

花了一点小时间入门了 kosaraju 算法。
记得之前在一篇博文中提到过，ACM中求强联通分量的常见算法有三种：

暴力
Tarjan
Kosaraju

其中暴力和 Kosaraju 算法在求强联通分量的同时，可以直接输出可行解，而Tarjan则需要通过额外的拓扑排序来得出可行解。

简单说一下 Kosaraju 的基本思路：
Kosaraju算法主要通过一个非常显然的性质来求强联通分量的。

对于一个强联通分量，将它的所有边反向，那么它依然是一个强联通分量。

因此，我们通过两边dfs，第一遍dfs求出整张图的拓扑序，第二遍dfs按照拓扑序通过反向边进行拓展。
这个地方就非常巧妙。因为在按照拓扑序遍历的过程中，对于一个点，如果它是一个强联通分量的一个点，那么除开原先遍历标记过点，必然会存在拓扑序在该点之后但仍然指向该点的一个点。

~~好难表达，yy很容易~~

题解

题意：
有一群牛，给你很多个关系，一对关系 a -> b 表示 a 认为 b 是肥宅，问被所有牛公认为肥宅的牛有几头。

思路：
题意即在拓扑序排最后一个强联通分量的数量。
注意，原图可能不联通，不联通根据题意输出0。

AC Code

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int max_v = 1e4 + 5;

int v_num, num;
vector<int> G[max_v], rG[max_v], vs;
bool vis[max_v];
int color[max_v];

void dfs(int u)
{
    vis[u] = true;
    int sz = G[u].size();
    for (int i = 0; i < sz; i++)
        if (!vis[G[u][i]])
            dfs(G[u][i]);
    vs.push_back(u);
}

void rdfs(int u, int scc)
{
    vis[u] = true;
    color[u] = scc;
    int sz = rG[u].size();
    for (int i = 0; i < sz; i++)
        if (!vis[rG[u][i]])
            rdfs(rG[u][i], scc);
}

int kosaraju()
{
    memset(vis, false, sizeof vis);
    vs.clear();
    for (int v = 1; v <= v_num; v++)
        if (!vis[v])
            dfs(v);
    memset(vis, false, sizeof vis);
    int scc = 0;
    num = 0;
    for (int i = vs.size() - 1; i >= 0; i--) {
        if (!vis[vs[i]])
            rdfs(vs[i], scc++);
    }
    int res = 0, u;
    for (int i = 1; i <= v_num; i++) {
        if (color[i] == scc - 1) {
            u = i;
            res++;
        }
    }
    memset(vis, false, sizeof vis);
    rdfs(u, 0);
    for (int i = 1; i <= v_num; i++)
        if (!vis[i])
            return 0;
    return res;
}

void addEdge(int from, int to)
{
    G[from].push_back(to);
    rG[to].push_back(from);
}

int main()
{
    int m, u, v;
    while (scanf("%d %d", &v_num, &m) != EOF) {
        for (int i = 1; i <= v_num; i++)
            G[i].clear(), rG[i].clear();
        while (m--) {
            scanf("%d %d", &u, &v);
            addEdge(u, v);
        }
        printf("%d\n", kosaraju());
    }
    return 0;
}

Kosaraju算法入门 ( 附 POJ 2186

NodeKey

算法详解

题解