求强连通分量 - 模板

using namespace std;

#define INF 0x3f3f3f3f
#define MAXN 1000010
#define MAXM 5010

inline int read()
{
    int x =  0,ff = 1;char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == ‘-‘) ff = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * ff;
}

int n,m,k,num = 0,ti = 0,top = 0,cnt = 0,dfn[MAXN],low[MAXN],cut[MAXN];
int lin[MAXN],tot = 1,vis[MAXN],id[MAXN],len[MAXN],ans[MAXN];
stack < int > scc;
struct edge
{
    int y,next;
}e[MAXN];

inline void add(int xx,int yy)
{
    e[++tot].y = yy;
    e[tot].next = lin[xx];
    lin[xx] = tot;
}

void Tarjan(int x)
{
    dfn[x] = low[x] = ++ti;
    scc.push(x); vis[x] = 1;
    for(int i = lin[x],y;i;i = e[i].next)
    {
        if(!dfn[y = e[i].y])
        {
            Tarjan(y);
            low[x] = min(low[x],low[y]);
        }
        else if(vis[y]) 
            low[x] = min(low[x],dfn[y]);
    }
        if(dfn[x] == low[x])
        {
            cnt++; int y;
            do
            {
                y = scc.top(); scc.pop();
                vis[y] = false;
                id[y] = cnt;   //点y属于哪一个连通分量
                len[cnt]++;　　//该连通分量的长度
            } while (x != y);
        }
}


int main()
{
    n = read(); m = read();
    for(int i = 1;i <= m;++i)
    {
        int x,y;
        x = read(); y = read(); 
        add(x,y);              //单向图
    }
    for(int i = 1;i <= n;++i)
    if(!dfn[i]) Tarjan(i);
    int l = 0;
    for(int i = 1;i <= cnt;++i)
    {
        if(l < len[id[i]])
        {
            k = i;
            l = len[id[i]];
        }
    }
    printf("%d\n",l);
    for(int i = 1;i <= n;++i)
    {
        if(id[i] == id[k])
        ans[++top] = i;
    }
    for(int i = 1;i < top;++i)
    printf("%d ",ans[i]);
    printf("%d",ans[top]);
    return 0;
}