强联通模板

#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
using namespace std;
const int MN=2011;

vector<int>edge[MN];
vector<int>SCC[MN];
stack<int>s;

int low[MN],dfn[MN];
int instack[MN],stap[MN];
int belong[MN];
int num[MN];
int ind[MN];
int tp,p;
int bcnt;

void tarjan(int x)
{
    low[x]=dfn[x]=++tp;
    stap[++p]=x;
    instack[x]=1;
    for(int i=0;i<edge[x].size();i++)
    {
        int v=edge[x][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            if(low[x]>low[v])
               low[x]=low[v];
        }
        else if(instack[v] && dfn[v]<low[x])
               low[x]=dfn[v];
    }
    if(low[x]==dfn[x])
    {
        int top;
        do
        {
            top=stap[p];
            belong[top]=bcnt;//缩点
            instack[top]=0;
            p--;
        }while(x!=top);
        bcnt++;
    }
}

void topsort()//求入度
{
    memset(num,0,sizeof(num));
    int i,u,v;
    while(!s.empty())
        s.pop();
    for(int i=0;i<bcnt;i++)
        if(ind[i]==0)
        {
            s.push(i);
            num[i]++;
        }
    while(!s.empty())
    {
        u=s.top();
        s.pop();
        for(int i=0;i<SCC[u].size();i++)
        {
            v=SCC[u][i];
            if(--ind[v]==0)
            {
                s.push(v);
                num[v]=num[u]+1;
            }
        }
    }
}

int main()
{
    int T,n,m,i,a,b,j;
    scanf("%d",&T);
    while(T--)
    {
        bcnt=tp=p=0;
        scanf("%d%d",&n,&m);
        memset(dfn,-1,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(instack,0,sizeof(instack));
        memset(belong,0,sizeof(belong));
        memset(ind,0,sizeof(ind));
        for(i=1;i<=n;i++)
        {
            edge[i].clear();
            SCC[i].clear();
        }
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            edge[a].push_back(b);
        }
        for(i=1;i<=n;i++)
        {
            if(dfn[i]==-1) tarjan(i);
        }
        for(i=1;i<=n;i++)//缩点后建图
        {
            for(j=0;j<edge[i].size();j++)
            {
                int x=belong[i];
                int y=belong[edge[i][j]];
                if(x!=y)
                {
                     SCC[x].push_back(y);
                     ind[y]++;
                }
            }
        }
        topsort();
        int ans=-1;
        for(i=0;i<bcnt;i++)
        {
            ans=max(ans,num[i]);
        }
        if(bcnt==ans) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}