L2-024. 部落（并查集）*

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<set>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<cstring>
 7 #include<string>
 8 using namespace std;
 9 
10 int pre[10005];
11 int f[10005];
12 
13 void init()
14 {
15     for(int i=0;i<10004;i++)
16         pre[i]=i,f[i]=0;
17 }
18 
19 int fin(int x)
20 {
21     return pre[x]==x?x:pre[x]=fin(pre[x]);
22 }
23 
24 
25 int main()
26 {
27     init();
28     int n,q,k,a,b;
29     cin>>n;
30     for(int i=0;i<n;i++)
31     {
32         cin>>k;
33         cin>>a;
34         f[a]=1;
35         for(int j=1;j<k;j++)
36         {
37             cin>>b;
38             f[b]=1;
39             int x=fin(a);
40             int y=fin(b);
41             if(x!=y)
42                 pre[x]=y;
43         }
44     }
45     int cnt=0,tot=0;
46     for(int i=0;i<10004;i++)
47     {
48         if(f[i]==1)
49         {
50             cnt++;
51             if(pre[i]==i)
52                 tot++;
53         }
54     }
55     printf("%d %d
",cnt,tot);
56     cin>>q;
57     for(int i=0;i<q;i++)
58     {
59         cin>>a>>b;
60         if(fin(a)==fin(b))
61             printf("Y
");
62         else
63             printf("N
");
64     }
65 
66     return 0;
67 }