PAT 1118

题目 ： Birds in Forest

分值 ： 25
难度 ： 并叉集
思路 ： 并叉集嘛
坑点 ： 一开始写在main里面的 计数变量忘记敷初值了 真尴尬

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
using namespace std;
int f[10001];
int flag[10001];
int find(int x)
{
    if(f[x]==0)
        return x;
    else
        return f[x] = find(f[x] ) ;
}
void Union(int a ,int b )
{
    int s1 = find(a) ;
    int s2 = find(b) ;
    if(s1 != s2)
        f[s2] = s1 ;
}

int main() {
    int N;
    cin >> N;
    for(int i = 0; i< N ; i++)
    {
        int times , temp , root ;
        cin >> times ;
        cin >> root ; flag[root] = 1 ;
        for(int j = 1 ; j < times ; j++)
        {
            cin >> temp;
            flag[temp] = 1 ;
            Union(root ,temp ) ;
        }
    }
    int sum_root= 0 , sum= 0  ;
    for(int i = 0 ; i < 10001 ;i ++)
    {
        if(!flag[i]) continue ;
        sum++ ;
        //cout <<i <<endl ;
        if(find(i) == i )
             sum_root ++ ;
    }
    cout << sum_root << " "<<sum <<endl ;
    int Q ,c1 ,c2 ;
    cin >> Q ;
    for(int i = 0 ; i< Q ; i++)
    {
        cin >> c1 >> c2 ;
        if(find(c1) == find(c2))
            cout << "Yes"<<endl ;
        else cout <<"No"<<endl ;
    }
}