poj 2762 Going from u to v or from v to u 判断图中任意两点x,y是否总是存在x->y或者y->x

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=100000;

struct edge

{

    int t,w;//u->t=w;

    int next;

};

int V,E;//点数(从1开始)，边数

int p[maxn],pf[maxn];//邻接表原图,逆图

edge G[maxn],Gf[maxn];//邻接表原图,逆图

int l,lf;

void init()

{

    memset(p,-1,sizeof(p));

    memset(pf,-1,sizeof(pf));

    l=lf=0;

}

void addedge(int u,int t,int w,int l)

{

    G[l].w=w;

    G[l].t=t;

    G[l].next=p[u];

    p[u]=l;

}

void addedgef(int u,int t,int w,int l)

{

    Gf[l].w=w;

    Gf[l].t=t;

    Gf[l].next=pf[u];

    pf[u]=l;

}

///Kosaraju算法,返回为强连通分量个数

bool flag[maxn]; //访问标志数组

int belg[maxn]; //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量

int numb[maxn]; //结束时间(出栈顺序)标记,其中numb[i]表示离开时间为i的顶点

//用于第一次深搜,求得numb[1..n]的值

void VisitOne(int cur, int &sig)

{

  flag[cur] = true;

  for (int i=p[cur];i!=-1;i=G[i].next)

  {

     if (!flag[G[i].t])

     {

         VisitOne(G[i].t,sig);

     }

  }

  numb[++sig] = cur;

}

//用于第二次深搜,求得belg[1..n]的值

void VisitTwo(int cur, int sig)

{

  flag[cur] = true;

  belg[cur] = sig;

  for (int i=pf[cur];i!=-1;i=Gf[i].next)

  {

     if (!flag[Gf[i].t])

     {

         VisitTwo(Gf[i].t,sig);

     }

  }

}

//Kosaraju算法,返回为强连通分量个数

int Kosaraju_StronglyConnectedComponent()

{

  int  i, sig;

  //第一次深搜

  memset(flag,0,sizeof(flag));

  for ( sig=0,i=1; i<=V; ++i )

  {

     if ( false==flag[i] )

     {

         VisitOne(i,sig);

     }

  }

  //第二次深搜

  memset(flag,0,sizeof(flag));

  for ( sig=0,i=V; i>0; --i )

  {

     if ( false==flag[numb[i]] )

     {

         VisitTwo(numb[i],++sig);

     }

  }

  return sig;

}

//缩点

int n;//缩点后的点个数1~n

int g[maxn];

edge eg[maxn];//邻接表

int re;

int in[maxn];//入度

int mat[1100][1100];//DAG的邻接矩阵

void dinit(int sig)

{

memset(g,-1,sizeof(g));

n=sig;

re=0;

memset(mat,0,sizeof(mat));

memset(in,0,sizeof(in));

}

void addedge0(int u,int t,int w,int l)

{

    eg[l].w=w;

    eg[l].t=t;

    eg[l].next=g[u];

    g[u]=l;

}

int topo[maxn];

int ct;

bool toposort()//缩点后拓扑排序肯定不存在环

{

ct=0;

int top=-1;

for(int i=1;i<=n;i++)

{

if(in[i]==0) in[i]=top,top=i;

}

for(int l=1;l<=n;l++)

{

int cur=top;

//if(top==-1) return 0;

top=in[top];

topo[ct++]=cur;

for(int i=g[cur];i!=-1;i=eg[i].next)

{

in[eg[i].t]--;

if(in[eg[i].t]==0) in[eg[i].t]=top,top=eg[i].t;

}

}

return 1;

}

int main()

{

int ci;scanf("%d",&ci);

while(ci--)

    {

        init();

        scanf("%d%d",&V,&E);

for(int i=1;i<=E;i++)

{

int u,t,w=1;scanf("%d%d",&u,&t);

addedge(u,t,w,l++);

addedgef(t,u,w,lf++);

}

        int ans=Kosaraju_StronglyConnectedComponent();

        //printf("%d/n",ans);

        ///缩点

        dinit(ans);

        for(int i=1;i<=V;i++)//构图

        {

        for(int j=p[i];j!=-1;j=G[j].next)

        {

        int st=belg[i],ed=belg[G[j].t];

        if(st!=ed)

        {

        int flag=1;

        for(int k=g[st];k!=-1;k=eg[k].next)

        {

        if(eg[k].t==ed)

        {

        flag=0;

        break;

        }

        }

        if(flag)

        {

        addedge0(st,ed,1,re++);

        mat[st][ed]=1;

        in[ed]++;

        }

        }

        }

        }

        //拓扑排序 如果拓扑序中任意第i个和第i+1个有边相连 则YES 否则NO

        toposort();

        int flag=1;

        for(int i=0;i<ct-1;i++)

        {

        int u=topo[i],v=topo[i+1];

        if(!mat[u][v])

        {

        flag=0;

        break;

        }

        }

        if(flag) printf("Yes/n");

        else printf("No/n");

    }

    return 0;

}

Description

In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the other. The son can either go from x to y, or from y to x. Wind promised that her tasks are all possible, but she actually doesn't know how to decide if a task is possible. To make her life easier, Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave, can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything?

Input

The first line contains a single integer T, the number of test cases. And followed T cases. The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly. 

Output

The output should contain T lines. Write 'Yes' if the cave has the property stated above, or 'No' otherwise.

Sample Input

1
3 3
1 2
2 3
3 1
      

Sample Output

Yes      

Description

In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the other. The son can either go from x to y, or from y to x. Wind promised that her tasks are all possible, but she actually doesn't know how to decide if a task is possible. To make her life easier, Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave, can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything?

Input

The first line contains a single integer T, the number of test cases. And followed T cases. 

The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly. 

Output

The output should contain T lines. Write 'Yes' if the cave has the property stated above, or 'No' otherwise.

Sample Input

1
3 3
1 2
2 3
3 1
      

Sample Output

Yes      

Description

In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the other. The son can either go from x to y, or from y to x. Wind promised that her tasks are all possible, but she actually doesn't know how to decide if a task is possible. To make her life easier, Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave, can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything?

Input

The first line contains a single integer T, the number of test cases. And followed T cases. 

The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly. 

Output

The output should contain T lines. Write 'Yes' if the cave has the property stated above, or 'No' otherwise.

Sample Input

1
3 3
1 2
2 3
3 1
      

Sample Output

Yes