pat 并查集题目代码详解

不得不吐槽并查集的题太少了

1118:

 1 //一道并查集查询的题目
 2 //需要注意的几个点
 3 //输入的时候在进行合并时，是一个一个输入的，所以需要引入一个变量来存储前一个输入的值（j!=1)
 4 //本题还要求输出树的数量和鸟的数量
 5 //那就统计有多少只鸟，用q记录
 6 //在查询鸟所在的树，并存入x
 7 //x的长度就是树的数量，q的长度就是鸟的数量
 8 #include<bits/stdc++.h>
 9 using namespace std;
10 #define int long long 
11 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
12 const int N=1e4+10;
13 int s[N];
14 int height[N];
15 set<int>q,x;
16 int n;
17 int c;
18 void init()
19 {
20     for(int i=1;i<=N;i++)
21     s[i]=i;
22 }
23 int find_s(int x)
24 {
25     if(x!=s[x])
26     {
27         s[x]=find_s(s[x]);
28     }    
29     return s[x];
30 }
31 void union_s(int x,int y)
32 {
33     x=find_s(x);
34     y=find_s(y);
35     if(height[x]==height[y])
36     {
37         height[x]++;
38         s[y]=x;
39     }
40     else
41     {
42         if(height[x]<height[y])
43         {
44             s[x]=y;
45         }
46         else
47         s[y]=x;
48     }
49 }
50 signed main()
51 {
52     IOS;
53     cin>>n;
54     init();
55     int ls=0;
56     int k,tmp;
57     for(int i=1;i<=n;i++)
58     {
59         cin>>k;
60         for(int j=1;j<=k;j++)
61         {
62             cin>>tmp;
63             q.insert(tmp);
64             if(j!=1)
65             {
66                 union_s(ls,tmp);
67             }
68             ls=tmp;
69         }
70         
71     }
72     for(auto &it:q)
73     {
74         int t=find_s(it);
75         x.insert(t);
76     }
77     cout<<x.size()<<" "<<q.size()<<endl;
78     cin>>c;
79     while(c--)
80     {
81         int a,b;
82         cin>>a>>b;
83         if(find_s(a)==find_s(b))
84         {
85             cout<<"Yes"<<endl;
86         }
87         else{
88             cout<<"No"<<endl;
89         }
90     }
91     return 0;
92 }

1107：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define int long long 
 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 5 const int N=1e4+10;
 6 int s[N];
 7 int height[N];
 8 int n;
 9 int course[N];
10 int cnt;
11 int isroot[N];
12 void init()
13 {
14     for(int i=1;i<=N;i++)
15     s[i]=i;
16 }
17 int find_s(int x)
18 {
19     if(x!=s[x])
20     {
21         s[x]=find_s(s[x]);
22     }    
23     return s[x];
24 }
25 void union_s(int x,int y)
26 {
27     x=find_s(x);
28     y=find_s(y);
29     if(height[x]==height[y])
30     {
31         height[x]++;
32         s[y]=x;
33     }
34     else
35     {
36         if(height[x]<height[y])
37         {
38             s[x]=y;
39         }
40         else
41         s[y]=x;
42     }
43 }
44 signed main()
45 {
46     IOS;
47     init();
48     cin>>n;
49     int tmp,k;
50     char c;
51     for(int i=1;i<=n;i++)
52     {
53         cin>>k>>c;
54         for(int j=1;j<=k;j++)
55         {
56             cin>>tmp;
57             if(course[tmp]==0)
58             {
59                 course[tmp]=i;
60             }
61             union_s(i,find_s(course[tmp]));
62         }
63     }
64     for(int i=1;i<=n;i++)
65     {
66         isroot[find_s(i)]++;
67     }
68     for(int j=1;j<=n;j++)
69     {
70         if(isroot[j]!=0)
71         {
72             cnt++;
73         }
74     }
75     cout<<cnt<<endl;
76     sort(isroot+1,isroot+1+n,greater<int>());
77     for(int i=1;i<=cnt;i++)
78     {
79         cout<<isroot[i];
80         if(i<cnt)
81             cout<<" ";
82     }
83     return 0;
84 }