P1017 （C++代码）

解题思路:

注意事项:

参考代码:

#include<iostream>
using namespace std;
int f[1001];  //a的朋友是f[a];  
 
int findroot(int a){  //找圈里的首领root 
	int i=a,root,temp;
	while(f[i]!=i) i=f[i];  
	root=i; //首领 
	
	i=a;
	while(i!=root){
		temp=f[i];
		f[i]=root;  
		i=temp;
	} //路径压缩 
	
	return root; 
}

int main(){
	int n,m;
	cin>>n>>m;
	
	//初试化，每个人都成立一个圈，首领就是自己	
	for(int i=1; i<=n; i++) f[i]=i;
	
	int x,y,result=0; 
    for(int i=0; i<n; i++) {  
        cin>>x>>y;  
		int fx=findroot(x),fy=findroot(y);//寻找各自的根节点  
    	if(fx!=fy) f[fx]=fy;//比较根节点，如果根节点不相同则进行合并在一个树中  
    	else result++;//如果两个有相同的根节点，说明冗余了     
    }
    cout<<result;
    return 0;
}