首页 > 代码库 > 1213 How Many Tables 简单的并查集问题

1213 How Many Tables 简单的并查集问题

my code:

#include <cstdio>
#include <cstring>
#include<iostream>
using namespace std;
int find(int num,int A []){
while(num!=A[num])//{
num = A[num];
return num;
}//

bool follow(int a,int b,int A[]){
int i = find(a,A);
int j = find(b,A);
//cout<<"zxd";
//cout<<i<<" "<<j<<" ";
if(i == j)return false;
//cout<<"zxd";
A[i] = j;
return true;
}


int main()
{
int t;
scanf("%d",&t);
while(t--){
//下面的两个变量是人数和关系两个变量
int m,n;
scanf("%d%d",&m,&n);
//在这里还是先创建一个动态数组,来保存返回值
int *A = new int [m+1];
for(int i = 1;i <= m;i++)A[i]=i;//for(int i = 1;i <= m;i++)cout<<A[i];

int a,b,count = 0;
for(int i = 0; i < n; i++){
scanf("%d%d",&a,&b);
// cout<<"循环中ing"<<a<<b<<endl;
if(follow(a,b,A))count++;
// cout<<"count++;"<<count<<endl;
}

printf("%d\n",m - count);
delete [] A;
}
return 0;
}

//在这里有两个关键的函数,也就是PPT中的

int find(int a) //查找根结点 { while(a != fa[a]) //我不是掌门 a = fa[a]; return a; }

int find(int a) //查找根结点 { while(a != fa[a]) //我不是掌门 a = fa[a]; return a; }