并查集——朋友圈，部落问题

7-2 朋友圈

某学校有N个学生，形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好，形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出，如果A和B是朋友，且B和C是朋友，则A和C也是朋友。请编写程序计算最大朋友圈中有多少人。

输入格式:

输入的第一行包含两个正整数N（≤30000）和M（≤1000），分别代表学校的学生总数和俱乐部的个数。后面的M行每行按以下格式给出1个俱乐部的信息，其中学生从1~N编号：

第i个俱乐部的人数Mi（空格）学生1（空格）学生2 … 学生Mi

输出格式:

输出给出一个整数，表示在最大朋友圈中有多少人。

输入样例:

7 4
3 1 2 3
2 1 4
3 5 6 7
1 6

输出样例:

4

/*并查集，就是把森林变成树，其中的依据就是题目的要求“朋友的朋友就是我的朋友”，
一开始让他们的根节点就是自己，然后通过第一步的join，让他们每个部落联系在一起，具有相同根节点，
find是找到其根节点的函数，并将他自己改成结点的值，便于后续的统计
#include<iostream>
#include<queue>
using namespace std;
const int N=3e4+5;
int n,m;
int res;
int pre[N],cnt[N];
int find(int x){
    while(x!=pre[x]) x=pre[x];
    return x;
}
void join(int x,int y){
    int px=find(x);
    int py=find(y);
    if(px!=py) pre[py]=px;
}
int main(){
cin>>n>>m;
    for(int i=1;i<=n;i++){   //初始化根结点为其自己，建造一棵棵树形成森林
        pre[i]=i;
    }
    while(m--){             //将每一组数联合成一个具有同一个根节点的树，实现森林变树
        int num;cin>>num;
        int fir;cin>>fir;
        num--;
        while(num--){
            int mem;cin>>mem;
            join(fir,mem);//在这个join里面，实现了把值改成了他的根节点的值，便于后续查找统计
        }
    }
    for(int i=1;i<=n;i++){  //统计具有相同根节点的过程，并把结果存在cnt里面
        int k=find(i);
        cnt[k]++;
    }
    for(int i=1;i<=n;i++){     找最大，然后输出
        res=max(res,cnt[i]);
    }
    cout<<res;
}

具体步骤

初始化

在初始化阶段，每个成员都是自己的祖先。

for (int i = 1; i <= n; i++) {
    pre[i] = i; // 每个成员的初始祖先是自己
}

处理第一组关系 "3 1 2 3"

这表示成员1、2、3有直接关联，我们需要将它们合并到同一个集合里。

1. 读取成员数量和第一个成员

    

   int num;
   cin >> num; // num = 3
   int fir;
   cin >> fir; // fir = 1

2. 合并剩下的成员

    

   num--; // num = 2 (因为第一个成员已经读入)
   while (num--) {
       int mem;
       cin >> mem; // 第一次循环 mem = 2, 第二次循环 mem = 3
       join(fir, mem); // 合并fir和mem所在的集合
   }

3. 合并过程

   • 第一次循环：mem = 2

      

     join(1, 2);

     • 查找1和2的根节点：  

       int find(int x) {
           while (x != pre[x]) x = pre[x];
           return x;
       }

       因为 pre[1] = 1 和 pre[2] = 2，所以根节点分别是1和2。
     • 合并根节点：  

       if (px != py) pre[py] = px; // pre[2] = 1

       合并后，pre数组变为 [1, 1, 3, 4, 5, 6, 7]。

   • 第二次循环：mem = 3

      

     join(1, 3);

     • 查找1和3的根节点： 因为 pre[1] = 1 和 pre[3] = 3，所以根节点分别是1和3。
     • 合并根节点：  

       if (px != py) pre[py] = px; // pre[3] = 1

       合并后，pre数组变为 [1, 1, 1, 4, 5, 6, 7]。

此时，成员1、2、3已经在同一个集合中了，它们的代表元素（根节点）都是1。

其他组关系处理

按照相同的逻辑处理其余组关系：

第二组关系 "2 1 4"

• 合并1和4所在的集合：  

  join(1, 4);

  • 查找1和4的根节点： 因为 pre[1] = 1 和 pre[4] = 4，所以根节点分别是1和4。
  • 合并根节点：  

    if (px != py) pre[py] = px; // pre[4] = 1

    合并后，pre数组变为 [1, 1, 1, 1, 5, 6, 7]。

第三组关系 "3 5 6 7"

• 合并5和6所在的集合：

   

  join(5, 6);

  • 查找5和6的根节点： 因为 pre[5] = 5 和 pre[6] = 6，所以根节点分别是5和6。
  • 合并根节点：  

    if (px != py) pre[py] = px; // pre[6] = 5

    合并后，pre数组变为 [1, 1, 1, 1, 5, 5, 7]。

• 合并5和7所在的集合：

   

  join(5, 7);

  • 查找5和7的根节点： 因为 pre[5] = 5 和 pre[7] = 7，所以根节点分别是5和7。
  • 合并根节点：  

    if (px != py) pre[py] = px; // pre[7] = 5

    合并后，pre数组变为 [1, 1, 1, 1, 5, 5, 5]。

第四组关系 "1 6"

• 已经包含在之前的关系中，无需再处理。

最终统计

通过 find 函数更新每个成员的根节点，并统计每个集合的大小：

for (int i = 1; i <= n; i++) {
    int k = find(i);
    cnt[k]++;
}

此时 cnt 数组应该为 [0, 4, 0, 0, 0, 3, 0, 0]，表示成员1、2、3、4在一个集合中，成员5、6、7在另一个集合中。

最终输出最大集合的大小：

for (int i = 1; i <= n; i++) {
    res = max(res, cnt[i]);
}
cout << res; // 输出 4

所以，最终输出结果为 4，表示具有最多直接和间接关联的成员数目为4。