Going from u to v or from v to u?

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 19234		Accepted: 5182

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?

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.

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

1

3 3

1 2

2 3

3 1

Yes

#include<iostream>//HiHo 1515

#include<cstdio>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<cstring>

#include<map>

#include<queue>

#include<stack>

#include<set>

#include<vector>

#include<algorithm>

#include<string.h>

typedef long long ll;

typedef unsigned long long LL;

using namespace std;

const int INF=0x3f3f3f3f;

const double eps=0.0000000001;

const int N=10000+10;

struct node{

    int to,next;

}edge[N<<1];

int tot;

int head[N];

int belong[N];

int dfn[N],low[N];

int cnt;

int vis[N];

int num;

vector<int>vc[N];

void init(){

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

    memset(low,0,sizeof(low));

    memset(dfn,0,sizeof(dfn));

    memset(vis,0,sizeof(vis));

    for(int i=1;i<N;i++)vc[i].clear();

    tot=0;

    num=0;

    cnt=0;

}

void add(int u,int v){

    edge[tot].to=v;

    edge[tot].next=head[u];

    head[u]=tot++;

}

stack<int>st;

void tarjan(int u){

    low[u]=dfn[u]=++num;

    vis[u]=1;

    st.push(u);

    for(int i=head[u];i!=-1;i=edge[i].next){

        int v=edge[i].to;

        if(dfn[v]==0){

            tarjan(v);

            low[u]=min(low[u],low[v]);

        }

        else if(vis[v]){

            low[u]=min(low[u],dfn[v]);

        }

    }

    if(low[u]==dfn[u]){

        int vv;

        cnt++;

        do{

            vv=st.top();

            st.pop();

            belong[vv]=cnt;

            vis[vv]=0;

        }while(vv!=u);

    }

}

queue<int>q;

int in[N];

void tuposort(){

    while(q.empty()==0){

        if(q.size()!=1){

            cout<<"No"<<endl;

            return;

        }

        int u=q.front();

        q.pop();

        for(int i=0;i<vc[u].size();i++){

            int v=vc[u][i];

            in[v]--;

            if(in[v]==0){

                q.push(v);

            }

        }

    }

    cout<<"Yes"<<endl;

    return;

}

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        int n,m;

        init();

        while(q.empty()==0)q.pop();

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

        scanf("%d%d",&n,&m);

        for(int i=1;i<=m;i++){

            int u,v;

            scanf("%d%d",&u,&v);

            add(u,v);

        }

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

            if(dfn[i]==0)tarjan(i);

        }

        //for(int i=1;i<=n;i++)cout<<belong[i]<<" ";cout<<endl;

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

            for(int j=head[i];j!=-1;j=edge[j].next){

                int uu=belong[i];

                int vv=belong[edge[j].to];

                if(uu!=vv){

                    vc[uu].push_back(vv);

                   // cout<<uu<<" "<<vv<<endl;

                    in[vv]++;

                }

            }

        }

        for(int i=1;i<=cnt;i++){

            if(in[i]==0){

                q.push(i);

            }

        }

        tuposort();

    }

}