C++(g++ 7.5.0) 解法, 执行用时: 88ms, 内存消耗: 3932K, 提交时间: 2022-10-14 19:38:47

#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define mod 998244353
#define N 400005
int n,m,k,cn,fa[N],ans[N];
int find(int x){
	if(x==fa[x])return x;
	int ff=find(fa[x]);
	if(ans[x]<ans[fa[x]])ans[x]=ans[fa[x]];
	return fa[x]=ff;
}
void join(int u,int v,int ew){
	int fu=find(u),fv=find(v);
	if(fu==fv)return;
	if(fu==1)swap(fu,fv);
	if(fv==1){
		fa[fu]=fv;
		ans[fu]=ew;
		return ;
	}
	ans[++cn]=ew;
	fa[fu]=fa[fv]=cn;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	cn=n;
	fr(i,1,n+n)fa[i]=i;
	fr(i,1,m){
		int u,v;
		scanf("%d%d",&u,&v);
		join(u,v,0);
	}
	fr(i,1,k){
		int u,v;
		scanf("%d%d",&u,&v);
		join(u,v,i);
	}
	fr(i,1,n){
		if(find(i)!=find(1))puts("-1");
		else printf("%d\n",ans[i]);
	}
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 705ms, 内存消耗: 20720K, 提交时间: 2022-12-04 22:40:19

#include<bits/stdc++.h>
using namespace std;
int b[200005];
vector<pair<int,int>>s[200005];
void bfs(int i,int ma)
{
    b[i]=ma;
    for(int j=0;j<s[i].size();j++)
    {
        int ma1=max(ma,s[i][j].second);
        if(b[s[i][j].first]==-1 || b[s[i][j].first]>ma1)
            bfs(s[i][j].first,ma1);
    }
}
int main(){
    memset(b,-1,sizeof(b));
    int n,x,y; cin>>n>>x>>y;
    for(int i=0;i<x;i++){
        int u,v; cin>>u>>v;
        s[u].push_back({v,0});
        s[v].push_back({u,0});
    }
    for(int i=1;i<=y;i++){
        int u,v; cin>>u>>v;
        s[u].push_back({v,i});
        s[v].push_back({u,i});
    }
    bfs(1,0);
    for(int i=1;i<=n;i++) cout<<b[i]<<endl;
}