C++14(g++5.4) 解法, 执行用时: 525ms, 内存消耗: 22496K, 提交时间: 2020-08-26 10:50:27

#include<iostream>
#include<cstring>
#include<map>
using namespace std;
int fa[105000], cnt[105000], ans[105000];
map<int, int>mp[105000];
int find(int x)
{
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int main()
{
	int n, m, q;
	while (cin >> n >> m >> q)
	{
		memset(cnt, 0, sizeof(cnt));
		memset(ans, -1, sizeof(ans));
		for (int i = 1;i <= n;i++)
		{
			mp[i].clear();
			fa[i] = i;
		}
		for (int i = 1;i <= n;i++)
		{
			int x;
			cin >> x;
			cnt[x]++;
			mp[i][x]++;
		}
		for (int i = 1;i <= q;i++)
		{
			int x, y;
			cin >> x >> y;
			x = find(x);
			y = find(y);
			if (mp[x].size() > mp[y].size())swap(x, y);
			fa[x] = y;
			for (auto it : mp[x])
			{
				mp[y][it.first] += it.second;
				if (mp[y][it.first] == cnt[it.first])ans[it.first] = i;
			}
		}
		for (int i = 1;i <= m;i++)
		{
			if (cnt[i] == 1)cout << 0 << endl;
			else cout << ans[i] << endl;
		}
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 205ms, 内存消耗: 16052K, 提交时间: 2023-02-10 14:42:27

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
map<int,int> mp[N];
int cnt[N],f[N],ans[N];
int find(int x)
{
	if(f[x]!=x) f[x]=find(f[x]);
	return f[x];
}
int main()
{
	int n,m,q,k;
	while(~scanf("%d%d%d",&n,&m,&q))
	{
		for(int i=1;i<=m;i++) ans[i]=-1,cnt[i]=0;
		for(int i=1;i<=n;i++) mp[i].clear();	
		for(int i=1;i<=n;i++)
		{
			f[i]=i;
			scanf("%d",&k);
			mp[i][k]++;
			cnt[k]++;
		}
		for(int i=1;i<=q;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			a=find(a),b=find(b);
			if(a!=b)
			{
				if(mp[a].size()>mp[b].size()) swap(a,b);
				f[a]=b;
				for(auto it:mp[a])
				{
					int x=it.first,y=it.second;
					mp[b][x]+=y;
					if(mp[b][x]==cnt[x]) ans[x]=i;
				}
			}
		}
		for(int i=1;i<=m;i++)
		{
			if(cnt[i]==1) printf("0\n");
			else printf("%d\n",ans[i]);
		}
	}
	return 0;
}