POJ2762Going from u to v or from v to u?

Time Limit: 2000MS Memory Limit: 65536K

Total Submissions: 13294 Accepted: 3460

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

题意：有N个山洞m条路，问任意两点x y 能否存在从x到y 或者从y到x。

思路：先对图求强连通分量，为每个连通块标号（如果有多个强连通分量），然后建缩点之后的图，图，即使代码中的G3，因为不同连通块间的标号不同，所以可以据此建图，G3就是一个DAG。

然后找到入度为零的点，如果个数大于等于2则这两个点无法连通（想想为什么），如果个数为1则进行

DAG上求最长路，如果最长路等于强连通的个数，则成立，否者条件不满足任意两点连通。

具体可以参考代码后的测试用数据。

#include   
#include   
#include   
#include   
#include   
#include   
#define DEBUG  
using namespace std;  
const int maxn = 1000+10;  
vector G[maxn], G2[maxn], G3[maxn];  
vector S;  
bool flag = false;  
  
int vis[maxn];  // for dfs1();  
int sccno[maxn], scc_cnt;  
bool mark[maxn];// for Track_path.  
int d[maxn]; // record the length of every vertex  (DAG). for Track_path().  
int gn, gm;  
  
  
void dfs1(int u) {  
    if(vis[u]) return;  
    vis[u] = 1;  
    for(int i = 0; i < (int)G[u].size(); i++) dfs1(G[u][i]);  
    S.push_back(u);  
}  
  
void dfs2(int u) {  
    if(sccno[u]) return;  
    sccno[u] = scc_cnt;  
    for(int i = 0; i < (int)G2[u].size(); i++) dfs2(G2[u][i]);  
}  
  
  
void find_scc(int n) {  
    scc_cnt = 0;  
    flag = false;  
    S.clear();  
    memset(sccno, 0, sizeof(sccno));  
    memset(vis, 0, sizeof(vis));  
    for(int i = 1; i <= gn; i++) dfs1(i);  
    for(int i = n-1; i >





= 0; i--) {  
        if(!sccno[S[i]]) {  
            scc_cnt++;  
            dfs2(S[i]);  
        }  
    }  
}  
  
void build_map() {  
    for(int i = 0; i < maxn; i++) {  
        G[i].clear(); G2[i].clear();  
    }  
    int u, v;  
    for(int i = 1; i <= gm; i++) {  
        scanf("%d%d", &u, &v); // directed graph.  
        G[u].push_back(v);  
        G2[v].push_back(u);  
    }  
}  
#ifndef DEBUG  
void mid_res() {  
    for(int i = 1; i <= gn; i++) {  
        printf("sccno[%d] = %d\n", i, sccno[i]);  
    }  
    cout << endl;  
}  
#endif  
  
  
void build_map2() {// build DAG。  
    for(int i = 0; i < maxn; i++) G3[i].clear();  
    for(int i = 1; i <= gn; i++) {  
        for(int j = 0; j < (int)G[i].size(); j++) {  
            if(sccno[i] != sccno[G[i][j]]) {  
                int u = sccno[i], v = sccno[G[i][j]];  
                G3[u].push_back(v);  
            }  
        }  
    }  
#ifndef   DEBUG  
    for(int i = 1; i <= scc_cnt; i++) {  
        for(int j = 0; j < (int)G3[i].size(); j++) {  
            printf("%d --> %d\n", i, G3[i][j]);  
        }  
    }  
#endif  
}  
  
void Track_path(int u) {  
    if(mark[u]) return;  
    mark[u] = true;  
    for(int i = 0; i < (int)G3[u].size(); i++) {  
        int v = G3[u][i];  
        if(!mark[v]) {  
            d[v] = d[u] + 1;  
            Track_path(v);  
        }  
    }  
}  
  
void work() {  
    bool tag[maxn];  
    memset(tag, false, sizeof(tag));  
    for(int i = 1; i <= gn; i++) {  
        if(tag[sccno[i]]) continue; // outdegree != 0.  
        for(int j = 0; j < (int)G2[i].size(); j++) {  
            if(sccno[i] != sccno[G2[i][j]]) {  
                tag[sccno[i]] = true; //  reverse graph outdegree > 0.  
                break;  
            }  
        }  
    }  
    vector ss;  
    ss.clear();  
    for(int i = 1; i <= scc_cnt; i++) {  
        if(tag[i] == false) {  
            ss.push_back(i);  
          //  printf("scc_cnt = %d\n", i);  
        }  
    }  
    if(ss.size() > 1) {  
        flag = false;  
        return;  
    }  
    build_map2();  
    memset(mark, false, sizeof(mark));  
    memset(d, 0, sizeof(d));  
    d[ss[0]] = 1;  
    Track_path(ss[0]);  
    int max_length = -1;  
    for(int i = 1; i <= scc_cnt; i++) {  
        max_length = max(max_length, d[i]);  
    }  
    if(max_length == scc_cnt) flag = true;  
    return;  
}  
  
int main()  
{  
    int T;  
    scanf("%d", &T);  
    while(T--) {  
        scanf("%d%d", &gn, &gm);  
        build_map();  
        find_scc(gn);  
       // mid_res();  
        work();  
        if(flag) printf("Yes\n");  
        else printf("No\n");  
    }  
    return 0;  
}  
/** 
4 
9 10 
1 2 
2 3 
3 1 
2 9 
8 9 
9 4 
4 5 
5 6 
6 7 
7 4 

4 4 
1 2 
1 3 
2 4 
3 4 

3 3 
1 2 
2 3 
3 1