POj2762 tarjan算法求强连通分量

题目大意：有n个房间，这些房间都有给定的路，现在要求任意两个房间能否相同(假设a与b相连通，那么只要满足a与b能够连通或者b与a能够连通即可)。，如果任意的两点能够连通输出Yes，否则输出No.

算法思路：明显的求强连通分量，再缩点，再对缩点后的图判断连通性(这里采用拓扑排序判断连通性，如果有2个及以上的点入度为0的点出现的话，说明缩点后的图是不连通的)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
int a[1005][1005],m,n,t,dfn[1005],low[1005],a2[1005][1005];
bool visited[1005],ins[1005],over,over2;
int l,r,cnt,times,group[1005];
int outdeer[1005],indeer[1005];
stack<int>stk;
void tarjan(int u)
{
    stk.push(u);
    ins[u]=true;
    dfn[u]=low[u]=times++;
    for(int i=1; i<=n; i++)
    {
        if(a[u][i])
        {
            if(!dfn[i])
            {
                tarjan(i);
                low[u]=min(low[u],low[i]);
            }
            else if(ins[i])
            {
                low[u]=min(low[u],dfn[i]);
            }
        }
    }
    int k;
    if(low[u]>=dfn[u])
    {

        do
        {
            k=stk.top();
            stk.pop();
            ins[k]=false;
            group[k]=cnt;

        }
        while(u!=k);

        cnt++;

    }

}

bool topusort()
{
    queue<int>que;
    int sum2=0;
    for(int i=1;i<cnt;i++)
    {
        if(indeer[i]==0)
        {
            visited[i]=true;
            sum2++;
            que.push(i);
        }
    }

    if(sum2>=2)
        return false;
    else if(sum2==1)
    {
        while(!que.empty())
        {
            sum2=0;
            int kk=que.front();
            que.pop();

            for(int i=1;i<cnt;i++)
            {
                if(a2[kk][i])
                {
                    indeer[i]--;
                    outdeer[kk]--;
                    a2[kk][i]=0;
                }
            }
            for(int i=1;i<cnt;i++)
            {
                if(!visited[i]&&indeer[i]==0)
                {
                    sum2++;
                    visited[i]=true;
                    que.push(i);
                }
            }
            if(sum2>=2)
                return false;


        }
    }

    return true;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        over=false;
        over2=true;
        memset(a,0,sizeof(a));
        memset(visited,false,sizeof(visited));
        memset(ins,false,sizeof(ins));
        memset(group,0,sizeof(group));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(outdeer,0,sizeof(outdeer));
        memset(indeer,0,sizeof(indeer));
        memset(a2,0,sizeof(a2));
        scanf("%d%d",&n,&m);

        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&l,&r);
            a[l][r]=1;
        }
        times=1;
        cnt=1;
        for(int i=1; i<=n; i++)
        {
            if(!dfn[i])
                tarjan(i);
        }
        if(!stk.empty())
        {
            while(!stk.empty())
            {
                int f=stk.top();
                stk.pop();
                group[f]=cnt;
            }
            cnt++;
        }

        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(a[i][j]&&group[i]!=group[j])
                {
                    outdeer[group[i]]++;
                    indeer[group[j]]++;
                    a2[group[i]][group[j]]=1;
                }
            }
        }
        // int sum1=0,sum2=0;
       if(topusort())
        printf("Yes\n");
       else
        printf("No\n");


    }

    return 0;
}