【模板】Kosaraju算法求强连通分量

#include<bits/stdc++.h>
#define MAX 5005
using namespace std;
int n,m,ord[MAX],s1=0,color[MAX],howmany=0;
bool vis[MAX]={0};
vector<int>G[MAX];
vector<int>T[MAX];
void dfs1(int u)
{
    vis[u]=1;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(vis[v])continue;
        vis[v]=1;
        dfs1(v);
    }
    ord[++s1]=u;
}
void dfs2(int u)
{
    vis[u]=1;
    color[u]=howmany;
    for(int i=0;i<T[u].size();i++)
    {
        int v=T[u][i];
        if(vis[v])continue;
        vis[v]=1;
        dfs2(v);
    }
}
int main()
{
    int a,b;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        T[b].push_back(a);
    }
    dfs1(1);
    memset(vis,0,sizeof vis);
    for(int i=n;i>0;i--)
    {
        if(!vis[ord[i]])
        {
            howmany++;
            dfs2(ord[i]);
        }
    }
    printf("%d\n",howmany);
    for(int i=1;i<=n;i++)printf("%d ",color[i]);
    return 0;
}