并查集例题

你的名字 2023-02-08 15:56 19阅读 0赞

**题目描述**  
假如已知有n个人和m对好友关系（存于集合r）。如果两个人是直接或间接的好友（好友的好友的好友…），则认为他们属于同一个朋友圈。请写程序求出这n个人里一共有多少个朋友圈。

**输入**  
输入包含多个测试用例，每个测试用例的第一行包含两个正整数 n、m，1 < = n，m< =100000。接下来有m行，每行分别输入两个人的编号f，t（1 < = f，t < = n），表示f和t是好友。 当n为0时，输入结束，该用例不被处理。

**输出**  
对应每个测试用例，输出在这n个人里一共有多少个朋友圈。每组一行。

**样例输入**

5 3
    1 2
    2 3
    4 5
    3 3
    1 2
    1 3
    2 3
    0

**样例输出**

2
    1

提示

例如，对于第一个例子：n = 5 ， m = 3 ， r = \{ \{1 , 2\} , \{2 , 3\} , \{4 , 5\}\}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，则1、2、3属于一个朋友圈，4、5属于另一个朋友圈，结果为2个朋友圈。

代码实现如下

#include<iostream>
    using namespace std;
    int f[100005],n, m,k,sum=0;
    void init()//先让每个人都知道自己，将其对应值给自己
    { 
        int i;
        for(i=1;i<=n;i++)
        { 
            f[i]=i;
        }
    }
    int getf(int v)//递归找到最大的朋友
    { 
        if(f[v]==v)
            return v;
        else { 
            f[v]=getf(f[v]);//压缩路径
            return f[v];
        }
    }
    void merge1(int v,int u)//合并两个圈子的函数
    { 
        int q1,q2;
        q1=getf(v);
        q2=getf(u);
        if(q1!=q2)//判断两个人是否否在同一个圈子。
        { 
            f[q2]=q1;//按靠左原则，即让右边的人成为做边的人；
     
        }
    }
    int main()
    { 
        int i,x,y;
        while(cin >> n,n)
        { 
            cin >>m;
        init();//初始化
        for(i=1;i<=m;i++)
        { 
            cin >> x >> y;//输入每个人关系
            merge1(x,y);//合并子集
        }
        for(i=1;i<=n;i++)//判断有几个团体；
        { 
            if(f[i]==i)
                sum++;
        }
        cout <<sum<<endl;
        sum=0;
     
        }
    }