POJ 2762 Going from u to v or from v to u? Tarjan缩点+判断链

Description

Input

Output

Sample Input

1
3 3
1 2
2 3
3 1

Sample Output

Yes

Source

//4616K	547MS
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define M 1007
using namespace std;
int dfn[M],low[M],head[M],vis[M],stack[M],belong[M];
int n,m,cnt,scnt,begin,num;
int g[M][M],in[M];
struct E
{
    int v,to;
}edg[M*M];
void init()
{
    memset(head,-1,sizeof(head));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(belong ,0,sizeof(belong));
    memset(stack,0,sizeof(stack));
    memset(vis,0,sizeof(vis));
    memset(g,0,sizeof(g));
    memset(in,0,sizeof(in));
    cnt=scnt=num=begin=0;
}
void addedge(int u,int v)
{
    edg[num].v=v;edg[num].to=head[u];
    head[u]=num++;
}
void tarjan(int x)
{
    int v;
    dfn[x]=low[x]=++cnt;
    stack[++begin]=x;
    for(int i=head[x];i!=-1;i=edg[i].to)
    {
        v=edg[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }
        else if(!vis[v])
            low[x]=min(low[x],dfn[v]);
    }
    if(low[x]==dfn[x])
    {
        scnt++;
        do
        {
            v=stack[begin--];
            belong[v]=scnt;
            vis[v]=1;
        }while(v!=x);
    }
}
bool link()//判断能否形成一条链
{
    queue<int>q;
    for(int i=1;i<=scnt;i++)
        if(!in[i])q.push(i);
    if(q.size()>1)return false;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=1;i<=scnt;i++)
            if(g[now][i])
            {
                in[i]--;
                if(!in[i])q.push(i);
            }
        if(q.size()>1)return false;
    }
    return true;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d%d",&n,&m);
        int a,b;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            addedge(a,b);
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i])tarjan(i);
        if(scnt==1) {printf("Yes\n");continue;}
        for(int u=1;u<=n;u++)//缩点之后，重新建图
            for(int j=head[u];j!=-1;j=edg[j].to)
            {
                int v=edg[j].v;
                if(u!=v&&belong[u]!=belong[v])
                {
                    g[belong[u]][belong[v]]=1;
                    in[belong[v]]++;
                }
            }
        if(link())printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}