|
传送门:牛客
题目描述:
愉快的周末到了，小C和他的N-1个朋友买了M个游戏，游戏编号从1~M。每个游戏都是多人游戏，他们打算周末一起打游戏。
小C的每个朋友都决定好了要玩哪一款游戏（会有一组人打同一款游戏），并且每人手上都有一台游戏机，这种游戏机可以通过特定的游戏机连接线连接起来。
但是，他们面临着一个问题：目前没有一个朋友的游戏机是互相连接的。所以它们必须用可用的游戏机连接线连接起来。小C决定依次使用第 i 条连接线把他的朋友 ui 和 vi 的游戏机连接起来。也就是说，假设有Q条连接线，小C只能先使用第一条，然后使用第二条，然后使用第三条。。。最后使用第Q条。
一个游戏能开始的条件是所有玩这个游戏的朋友的游戏机都被连接起来（如果不是直接连接的话，那么就必须存在一条连接它们的路径）。他们希望尽快开始比赛。
在每个游戏中，找出在添加了第几条连接线之后能开始游戏。如果在一个游戏中只有一个人玩，则输出0（因为他立马可以开始游戏）。如果不存在，则输出-1
输入:
5 2 4
1 2 2 2 1
1 2
2 3
1 5
4 5
输出:
3
4
首先读完题我们应该就可以看出来这是一道并查集的题目,并且显然的我们脑中应该会有这样的一个想法:每一次加入连线时,我们就将两个并查集合并,并且更新大的并查集中的每一个游戏的参与人数,判断是否满足条件,满足输出即可
经过分析之后我们会发现这一种做法是可行的,但是因为游戏的数量M和N太大,并且每一个人又只能有一个喜欢的游戏,如果我们开数组的话空间会被大量浪费,并且会导致MLE,此时的解决办法是离散化,但是对于离散化我们往往会有一种比较偷懒的一种解决方案,那就是使用我们的map(在这道题中我们准备开二维的map).
因为我们需要遍历map中的数据,因此我们还需要学习迭代器的知识(有点像C语言中的指针??)
对于map,我们的迭代器为map<int,int>::iterator [name]然后在for中使用
for(it = map.begin();it!=map.end;it++)
在for循环中,我们可以采用简便方法遍历auto it : [name]
在迭代器中,指针的第一个参数first代表map中的第一个值,second代表第二个值
下面是具体的代码部分(包含了迭代器的两种写法):
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n,m,q;int fa[maxn];
map<int,int>x[100005];
int ans[maxn];int cnt[maxn];
int find(int a) {
if(a==fa[a]) return a;
else return fa[a]=find(fa[a]);
}
map<int,int>::iterator it;
int main() {
while(scanf("%d%d%d",&n,&m,&q)!=EOF) {
memset(ans,0,sizeof(ans));
for(int i=1;i<=n;i++) x[i].clear();
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++) fa[i]=i;
int num;
for(int i=1;i<=n;i++) {
num=read();
cnt[num]++;
x[i][num]++;
}
int u,v;
for(int i=1;i<=q;i++) {
u=read();v=read();
int uu=find(u),vv=find(v);
if(uu==vv) continue;
if(x[uu].size()>x[vv].size()) {
swap(u,v);
swap(uu,vv);
}
fa[uu]=vv;
for(it=x[uu].begin();it!=x[uu].end();it++) {
x[vv][it->first]+=it->second;
if(x[vv][it->first]==cnt[it->first]&&ans[it->first]==0) {
ans[it->first]=i;
}
}
}
for(int i=1;i<=m;i++){
if(cnt[i]==1) printf("0\n");
else if(ans[i]==0) printf("-1\n");
else printf("%d\n",ans[i]);
}
}
return 0;
}
|