首页 > 代码库 > PAT A 1118. Birds in Forest (25)

PAT A 1118. Birds in Forest (25)

并查集合并

#include<iostream>using namespace std;const int MAX = 10010;int father[MAX],root[MAX];int findfather(int x){	if(x==father[x]) return x;	else{		int F=findfather(father[x]);		father[x]=F;		return F;	}}void Union(int a , int b){	int faA=findfather(a);	int fbB=findfather(b);	if(faA!=fbB){		father[faA]=fbB;	} }void init(){	for(int i=0;i<MAX;i++){		father[i]=i;		root[i]=0;	}} int n,q;int main(){	init();	cin>>n;	int maxbirds=0; 	for(int i=0;i<n;i++){		int nbirds,firstbird;		scanf("%d%d",&nbirds,&firstbird);		if(firstbird>maxbirds) maxbirds=firstbird;		for(int j=1;j<nbirds;j++){			int bird;			scanf("%d",&bird);			if(bird>maxbirds) maxbirds=bird;			Union(firstbird,bird);		}	}	int trees=0;	for(int i=1;i<=maxbirds;i++){		int fa=findfather(i);		root[fa]++;		if(root[fa]==1) trees++;	}	printf("%d %d\n",trees,maxbirds);	cin>>q;	while(q--){		int a , b;		scanf("%d%d",&a,&b);		if(findfather(a)==findfather(b)) printf("Yes\n");		else printf("No\n");	}}

非递归压缩并查集

int father[MAX];  bool isRoot[MAX];//判根    int findFather( int x ) {      int a = x;      while( x != father[x] ) {          x = father[x];      }        while( a != father[a] ) {          int z = a;          a = father[a];          father[z] = x;      }      return x;  }    void Union( int a, int b ) {      int faA = findFather( a );      int faB = findFather( b );        if( faA != faB ) {          father[faA] = faB;      }  }    void init( int n ) {      for( int i = 1; i <= n; i++ ) {  //从1开始        father[i] = i;          isRoot[i] = false;      }  }  

PAT A 1118. Birds in Forest (25)