[POJ 2762]Going from u to v or from v to u? (強連通分量+拓撲排序)

[POJ 2762]Going from u to v or from v to u? (強連通分量+拓撲排序)

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

Source

POJ Monthly--2006.02.26,zgl & twb

題目大意：給定一個有向圖，判斷圖中任意兩點u,v是否能從u到達v或從v到達u，可以的話輸出Yes，不行輸出No

注意這裡是或者不是而且，如果是而且的話直接判斷整個圖是不是一個強連通分量即可，簡單很多，此題的思路是先將整圖縮點(每個強連通分量中任意兩點均可達)，對縮點後的DAG進行拓撲排序，在排序過程中若出現多個入點為0的點則判定排序失敗，若最終拓撲排序成功則表明圖中任意兩點u,v能從u到達v或從v到達u

#include 
#include 

#define MAXV 8010
#define MAXE 2010
#define cls(array,num) memset(array,num,sizeof(array))

using namespace std;

struct edge
{
    int u,v,next;
}edges[MAXV],newedges[MAXV];

int head[MAXE],dfn[MAXE],low[MAXE],belong[MAXE],stack[4*MAXE],inDegree[MAXE];
bool inStack[MAXE];
int top=0,nCount=0,newCount=0,tot=0,index=0,n,m;

int min(int a,int b)
{
    if(a1) return false;
    int rest=tot,result[MAXE];
    while(rest--)
    {
        ans=0;
        for(int p=head[num];p!=-1;p=newedges[p].next)
        {
            int v=newedges[p].v;
            inDegree[v]--;
            if(inDegree[v]==0)
            {
                ans++;
                num=v;
            }
        }
        if(ans>1) return false;
    }
    return true;
}

int main()
{
    int testCase;
    cin>>testCase;
    while(testCase--)
    {
        cls(head,-1);
        cls(dfn,0);
        cls(low,0);
        cls(stack,0);
        cls(inStack,0);
        cls(belong,0);
        cls(inDegree,0);
        top=0,nCount=0,newCount=0,tot=0,index=0;
        for(int i=0;i>n>>m;
        for(int i=1;i<=m;i++)
        {
            int a,b;
            cin>>a>>b;
            AddEdge(a,b,edges,nCount);
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i]) tarjan(i);
        newGraph();
        if(topologicalSort())
            cout<<"Yes"<