poj 2762 Going from u to v or from v to u?

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 19390 Accepted: 5224
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

解题思路

首先如果是一个环，那么这些点一定能互相到达，所以先缩点。缩完点之后就形成了一棵树，如果两个点入度都为0，那么他们一定不可能到达对方，所以拓补排序，每次看是否有两个点同时入度为0。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;
const int MAXM = 100005;
const int MAXN = 10005;

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}

int n,m,T;
int num,col_num,col[MAXN];
int dfn[MAXN],low[MAXN];
int head[MAXN],cnt,fr[MAXM],se[MAXM];
int to[MAXM],nxt[MAXM];
int head_[MAXN],cnt_;
int to_[MAXM],nxt_[MAXM];
int stk[MAXN],top,du[MAXN];
bool vis[MAXN];
queue<int> Q;

inline void add(int bg,int ed){
    to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;
}

inline void add_(int bg,int ed){
    to_[++cnt_]=ed,nxt_[cnt_]=head_[bg],head_[bg]=cnt_;
}

inline void tarjan(int x){
    dfn[x]=low[x]=++num;
    stk[++top]=x;vis[x]=1;
    for(register int i=head[x];i;i=nxt[i]){
        int u=to[i];
        if(!dfn[u]){
            tarjan(u);
            low[x]=min(low[x],low[u]);
        }
        else if(vis[u])
            low[x]=min(low[x],dfn[u]);
    }
    if(low[x]==dfn[x]){
        vis[x]=0;col[x]=++col_num;
        while(stk[top]!=x){
            vis[stk[top]]=0;
            col[stk[top--]]=col_num;
        }
        top--;
    }
}

int main(){
    T=rd();
    while(T--){
        bool flag=0;
        for(register int i=1;i<=10000;i++)
            dfn[i]=low[i]=col[i]=du[i]=vis[i]=head[i]=head_[i]=0;
        cnt=top=0;num=col_num=0;
        while(Q.size()) Q.pop();
        n=rd();m=rd();
        for(register int i=1;i<=m;i++){
            int x=rd(),y=rd();
            add(x,y);
            fr[i]=x;se[i]=y;
        }
        for(register int i=1;i<=n;i++)
            if(!dfn[i]) tarjan(i);
        for(register int i=1;i<=m;i++)
            if(col[fr[i]]!=col[se[i]])  
                add_(col[fr[i]],col[se[i]]),du[col[se[i]]]++;
        for(register int i=1;i<=col_num;i++)
            if(!du[i]){
                if(Q.size()) {flag=1;break;}
                Q.push(i);
            } 
        if(flag==1) {puts("No");continue;}
        while(Q.size()){
            int x=Q.front();Q.pop();
            for(register int i=head_[x];i;i=nxt_[i]){
                int u=to_[i];
                du[u]--;
                if(du[u]==0){
                    if(Q.size()) {flag=1;break;}
                    Q.push(u);
                }
            }
            if(flag==1) break;
        }
        if(flag==1) puts("No");
        else puts("Yes");
    }
    return 0;
}