蓝桥杯2017年第八届真题-合根植物 （C++代码）

解题思路:

注意事项:

参考代码:

#include<iostream>

#define maxn 1000010

using namespace std;

int pre[maxn];

int n,m,k,cnt;

int find(int x){

int temp=x;

while(temp!=pre[temp]){

temp=pre[temp];

}

int t;

while(temp!=x){

t=pre[x];

pre[x]=temp;

x=t;

}

return temp;

}

int join(int a,int b){

int aa=find(a);

int bb=find(b);

if(aa!=bb){

pre[bb]=pre[aa];

cnt--;

}

}

int main(){

cin>>n>>m;

cnt=n*m;

for(int i=0;i<=n*m;i++){

pre[i]=i;

}

cin>>k;

for(int i=0;i<k;i++){

int a,b;

cin>>a>>b;

join(a,b);

}

cout<<cnt<<endl;

return 0;

}