A

A - How Many Tables

实现1代码：

 1 /***********************************************/
 2 #define set st
 3 int set[1006];
 4 int n,m;
 5 void join(int a,int b)
 6 {
 7     int fa=set[a];
 8     int fb=set[b];
 9     if(fa>fb) swap(fa,fb);
10     for(int i=1;i<=n;i++)
11     {
12         if(set[i]==fb) set[i]=fa;
13     }
14 }
15 
16 int main()
17 {
18     int t;
19     cin>>t;
20     while(t--)
21     {
22         cin>>n>>m;
23         for(int i=1;i<=n;i++) set[i]=i;
24         int a,b;
25         for(int i=1;i<=m;i++)
26         {
27             sc2(a,b);
28             join(a,b);
29         }
30         int cur=0;
31         int vis[1007];
32         mem0(vis);
33         for(int i=1;i<=n;i++){
34             if(vis[set[i]]==0) {
35                 cur++;
36                 vis[set[i]]=1;
37             }
38         }
39         cout<<cur<<endl;
40     }
41     return 0;
42 }

View Code

实现2代码：（建成树）

 1 /***********************************************/
 2 #define set st
 3 int set[1006];
 4 int n,m;
 5 
 6 int find(int a)
 7 {//找a所在并查集的根 
 8     while(set[a]!=a)
 9     {
10         a=set[a];
11     }
12     return a;
13 }
14 
15 void join(int a,int b)
16 {//将a和b所在的并查集合并 
17     int fa=find(a);
18     int fb=find(b);
19     if(fa>fb) set[fa]=fb;
20     else set[fb]=fa;
21 }
22 
23 int main()
24 {
25     int t;
26     cin>>t;
27     while(t--)
28     {
29         cin>>n>>m;
30         for(int i=1;i<=n;i++) set[i]=i;
31         int a,b;
32         for(int i=1;i<=m;i++)
33         {
34             sc2(a,b);
35             join(a,b);//将a和b所在的并查集合并 
36         }
37         int ans=0;
38         for(int i=1;i<=n;i++)
39         {
40             if(set[i]==i) ans++;
41         }
42         cout<<ans<<endl;
43     }
44     return 0;
45 }

View Code