경기 코드'Best Coder'배 중국 대학생 프로그램 디자인 챔피언십 1009-인접표 + 검색-Exploration

Problem Description
Miceren likes exploration and he found a huge labyrinth underground!
This labyrinth has N caves and some tunnels connecting some pairs of caves.
There are two types of tunnel, one type of them can be passed in only one direction and the other can be passed in two directions. Tunnels will collapse immediately after Miceren passing them.
Now, Miceren wants to choose a cave as his start point and visit at least one other cave, finally get back to start point.
As his friend, you must help him to determine whether a start point satisfing his request exists.
Input
The first line contains a single integer T, indicating the number of test cases.
Each test case begins with three integers N, M1, M2, indicating the number of caves, the number of undirectional tunnels, the number of directional tunnels.
The next M1 lines contain the details of the undirectional tunnels. Each line contains two integers u, v meaning that there is a undirectional tunnel between u, v. (u ≠ v)
The next M2 lines contain the details of the directional tunnels. Each line contains integers u, v meaning that there is a directional tunnel from u to v. (u ≠ v)
T is about 100.
1 ≤ N,M1,M2 ≤ 1000000.
There may be some tunnels connect the same pair of caves.
The ratio of test cases with N > 1000 is less than 5%.
Output
For each test queries, print the answer. If Miceren can do that, output "YES", otherwise "NO".
Sample Input

2

5 2 1

1 2

1 2

4 5

4 2 2

1 2

2 3

4 3

4 1

Sample Output

YES

NO

Hint
If you need a larger stack size, please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.
대의: 그림에 고리가 있는지 없는지를 판정하고 무방향도에 대해서는 조사집을 사용하며 유방향도에 대해서는 topo로 판정한다. 만약에 이 두 점에 같은 아버지 결점이 있다면 하나의 고리라는 것을 설명한다. 그렇지 않으면 그들을join과 함께 한다. topo는 인접표로 아날로그 체인표보다 편리하게 실현한다. 그리고 조사한 세 가지 함수를 복습하고 조사했다.

#include<cstdio>

#include<cstring>

#include<vector>

#include<algorithm>

#include<queue>

using namespace std;

const int MAX = 1e6 + 10;

int ans[MAX],in[MAX];

int n,m1,m2;

int p[MAX];

vector<int> G[MAX];

int find(int x)

{

    return (x == p[x])? x:p[x] = find(p[x]);

}

void join(int x,int y)

{

  int fx = find(x);

  int fy = find(y);

  if(fx != fy)

      p[fx] = fy;

}

int judge(int x,int y)

{

    return find(x) == find(y) ? 1 :0;

}



int topo()

{

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

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

     for(int j = 0 ; j < G[i].size();j++)

         in[G[i][j]]++;

 queue<int> q;

 while(!q.empty())

     q.pop();

 int cnt = 1;

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

     if(!in[i]) 

        q.push(i);

while(!q.empty()){

    int u = q.front();

    q.pop();

    ans[cnt++] = u;

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

        int v = G[u][i];

        in[v]--;

        if(!in[v]) 

            q.push(v);

    }

}

if(cnt == n ) return 0;

else return 1;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d%d",&n,&m1,&m2);

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

            p[i] = i;

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

            G[i].clear();

    int flag = 0;

    int u,v;

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

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

        if(judge(u,v) == 1) {

            flag = 1;

           break;       

        }

        else    join(u,v);

    }

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

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

        if(judge(u,v) == 1){

            flag = 1;

            break;

        }

        if(flag == 1)

            break;

        G[u].push_back(v);

    }

    if(flag == 1) {printf("YES
");continue;}

    if(topo() == 1) {

        printf("NO
");

    }

    else printf("YES
");

    }

    return 0;

}