kosaraju算法，comp with tarjan，复杂度差不多，写法较易，局限性较高

例题： popular cow

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#define INF 99999999
using namespace std;
int n, m, cnt;
int InNum[10005];//强连通分量的节点个数
bool vis[10005];//判重
int FaNam[10005];//节点隶属的强连通分量的编号
vector<int> e[10005];//正图
vector<int> re[10005];//反图
vector<int> s;//栈
void dfs1(int x) {
    vis[x] = 1;//标记入栈

    for(int i = 0; i < e[x].size(); i++)
        if(!vis[e[x][i]])
            dfs1(e[x][i]);//扩展入栈节点

    s.push_back(x);//入栈
}
void dfs2(int x) {
    FaNam[x] = cnt;//标记x隶属的强连通分量为cnt
    InNum[cnt]++;//编号为cnt的连通分量个数多一个
    vis[x] = 1;//x已入强连通分量

    for(int i = 0; i < re[x].size(); i++)
        if(!vis[re[x][i]])
            dfs2(re[x][i]);//如果re[x][i]没有进入强连通分量
}

void Kosaraju() {
    memset(vis, 0, sizeof(vis));

    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < e[i].size(); j++) {//检查强连通分量的出度
            int w = e[i][j];

            if(FaNam[i] != FaNam[w])
                vis[FaNam[i]] = 1;//设其为一
        }
    }

    int ans;
    int t = 0;

    for(int i = 1; i <= cnt; i++) {//检查有几个强连通分量的出度为0
        if(!vis[i]) {
            ans = i;
            t++;
        }
    }

    if(t == 1) 
    //如有多个出度为零，显然不符合要求，不然就有编号为ans的强连通分量OK
        printf("%d\n", InNum[ans]);
    else
        printf("0\n");
}

int main() {
    int a, b;
    scanf("%d%d", &n, &m);

    for(int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        e[a].push_back(b);
        re[b].push_back(a);
    }

    for(int i = 1; i <= n; i++)
        if(!vis[i])
            dfs1(i);

    memset(vis, 0, sizeof(vis));
    memset(InNum, 0, sizeof(InNum));
    cnt = 0;

    for(int i = s.size() - 1; i >= 0; i--) {
        if(!vis[s[i]]) {
            cnt++;
            dfs2(s[i]);
        }
    }

    Kosaraju();

    return 0;
}

kosaraju算法

原文：https://www.cnblogs.com/yangxuejian/p/10759304.html