P1017 （C++代码）

解题思路:





注意事项:





参考代码:

#include<iostream>  
using namespace std;  
int pre[1001];  
int sum;  
int find(int x){  
    int r=x;  
    while(r!=pre[r])  
        r=pre[r];  
        int i=x,j;  
        while(i!=r)//路径压缩  
        {  
            j=pre[i];  
            pre[i]=r;  
            i=j;  
        }  
    return r;  
}  
void join (int x,int y)  
{  
    int fx=find(x),fy=find(y);//寻找各自的根节点  
    if(fx!=fy)//比较根节点，如果根节点不相同则进行合并在一个树中  
    pre[fx]=fy;  
    else sum++;//如果两个有相同的根节点，说明冗余了  
}  
  
int main()  
{  
    int n,m;  
    int x,y;  
    cin>>n>>m;  
    for(int i=0;i<=1000;i++)  
        pre[i]=i;  
    for(int i=0;i<n;i++)  
    {  
        cin>>x>>y;  
        join(x,y);//输入两个数直接比较他们的上级;进行连接操作  
  
    }  
    cout<<sum;  
  
}