警告
本文最后更新于 2023-07-07,文中内容可能已过时。
并查集求连通域数目,初始化 sum=n;
题目链接: how many tables
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
| #include<bits/stdc++.h>
using namespace std;
int pre[1005];
int find(int root){
int son,t;
son=root;
while(root!=pre[root])
root=pre[root];
while(son!=root){
t=pre[son];
pre[son]=root;
son=t;
}
return root;
}
int main(){
int n,m,t,sum,root1,root2;
cin>>t;
while(t--){
cin>>n>>m;
sum=n;
for(int i=1;i<=n;i++)
pre[i]=i;
for(int i=0;i<m;i++){
cin>>root1>>root2;
int xx=find(root1);
int yy=find(root2);
if(xx!=yy){
pre[xx]=yy;
sum--;
}
}
cout<<sum<<endl;
}
return 0;
}
|