分组并查集的合并处理

题目描述

愉快的周末到了，小C和他的N-1个朋友买了M个游戏，游戏编号从1~M。每个游戏都是多人游戏，他们打算周末一起打游戏。

小C的每个朋友都决定好了要玩哪一款游戏（会有一组人打同一款游戏），并且每人手上都有一台游戏机，这种游戏机可以通过特定的游戏机连接线连接起来。

但是，他们面临着一个问题：目前没有一个朋友的游戏机是互相连接的。所以它们必须用可用的游戏机连接线连接起来。小C决定依次使用第 i 条连接线把他的朋友 ui 和 vi 的游戏机连接起来。也就是说，假设有Q条连接线，小C只能先使用第一条，然后使用第二条，然后使用第三条。。。最后使用第Q条。

一个游戏能开始的条件是所有玩这个游戏的朋友的游戏机都被连接起来（如果不是直接连接的话，那么就必须存在一条连接它们的路径）。他们希望尽快开始比赛。

在每个游戏中，找出在添加了第几条连接线之后能开始游戏。如果在一个游戏中只有一个人玩，则输出0（因为他立马可以开始游戏）。如果不存在，则输出-1

输入描述:

多组输入

第一行包含三个整数N，M，Q。

第二行给N个用空格分隔的整数，第 i 个整数代表第 i 个朋友想玩的游戏。

接下来的Q行，每行两个整数(u, v)，代表电线 i 连接的两个人的电脑

1 <= N, M <= 10^5
0 <= Q <= 10^5

输出描述:

对于每个游戏，输出一个整数，表示添加了第几条连接线之后能开始游戏，每行以换行符结束

示例1

输入

复制

输出

复制

3
4

说明

**样例解释**

第一个游戏有两个人参加（1，5），在添加了第三条电线之后他们电脑互相连接

第二个游戏三个人参加（2， 3， 4），在添加第四条电线之后他们电脑互相连接

题目解析

开始时朋友们的电脑都没有相互连接,然后给出了连接的方案,判断连接第几条的时候打一个游戏的所有朋友可以同时连接或者间接连接,注意看样例说明

难点是有多个游戏数据量大,怎样判断玩不同游戏的好友是否同时间接或直接连接

解题思路感谢楼上大佬

但是问题在于普通的并查集默认所有的人都是一组，像这样多组的情况有点像食物链那道题，如果你做过那就很容易想到，其实说白了就是把普通并查集里的一个集合给扩展，现在我这一个集合不仅保存了连接起来的人，还保存了每个人的游戏组别，合并的时候只要把这些属性一起合并就好了

代码解析

二维map存放每一个朋友玩的游戏,把每一个朋友看成一个独立的小组然后通过每一根线的合并进行操作判断第i个游戏的朋友是否全部连接

AC代码

#include <bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(0);
const int maxn=1e5+5;
map<int ,int >mp[maxn];//二维map,防爆二维数组
int n,m,q;//表示n个朋友,m个游戏,q条连接
int pre[maxn],num[maxn];//并查集数组
int ans[maxn],cnt[maxn];//按序统计答案,和统计每一游戏的人数
void init(int n){//多组输入进行初始化
    for(int i=1;i<=n;++i){
        pre[i]=i;
        num[i]=1;
        mp[i].clear();
        ans[i]=0;
        cnt[i]=0;
    }
}
int find(int x){
    if(pre[x]==x) return x;
    return pre[x]=find(pre[x]);
}
int main(){
    IOS;
    while(cin>>n>>m>>q){
        init(n);
        for(int i=1;i<=n;++i){
            int t;cin>>t;
            mp[i][t]++;//分组统计人数
            cnt[t]++;//统计玩某一个游戏的人数
        }
        for(int i=1;i<=q;++i){
            int x,y;
            cin>>x>>y;
            int fx=find(x);
            int fy=find(y);
            if(fx==fy) continue;
            if(num[fx]>num[fy]) swap(fx,fy);
            pre[fx]=fy;
            num[fy]+=num[fx];
            for(auto it:mp[fx]){//将x组的人数全部移动到y组,迭代器
                mp[fy][it.first]+=it.second;
                if(mp[fy][it.first]==cnt[it.first])
                    ans[it.first]=i;
            }
        }
        for(int i=1;i<=m;++i){
            if(cnt[i]==1){
				cout<<0<<endl;
			}else if(ans[i]==0){//到死也玩不上，呜呜呜
				cout<<-1<<endl;
			}else{
				cout<<ans[i]<<endl;
			}	
        }
    }
    return 0;
}

题解 | #小C的周末#