Submission #2529813

---

Source Code Expand

#include<iostream>
using ll = long long;
#define MAX_N 201010
using namespace std;

ll par_way[MAX_N],r_way[MAX_N];
ll par_train[MAX_N],r_train[MAX_N];

void init_way(ll n){
	for(ll i=0;i<n;i++){
		par_way[i] = i;
		r_way[i] = 0;
	}
}

ll find_way(ll x){
	if(par_way[x] == x){
		return x;
	}else{
		return par_way[x] = find_way(par_way[x]);
	}
}

void unite_way(ll x,ll y){
	x = find_way(x);
	y = find_way(y);
	if(x==y)	return;
	if(r_way[x]<r_way[y]){
		par_way[x] = y;
	}
	else{
		par_way[y] = x;
		if(r_way[x] == r_way[y])	r_way[x]++;
	}
}

bool same_way(ll x,ll y){
	return find_way(x) == find_way(y);
}

void init_train(ll n){
	for(ll i=0;i<n;i++){
		par_train[i] = i;
		r_train[i] = 0;
	}
}

ll find_train(ll x){
	if(par_train[x] == x){
		return x;
	}else{
		return par_train[x] = find_train(par_train[x]);
	}
}

void unite_train(ll x,ll y){
	x = find_train(x);
	y = find_train(y);
	if(x==y)	return;
	if(r_train[x]<r_train[y]){
		par_train[x] = y;
	}
	else{
		par_train[y] = x;
		if(r_train[x] == r_train[y])	r_train[x]++;
	}
}

bool same_train(ll x,ll y){
	return find_train(x) == find_train(y);
}

int main(void){
	ll N,K,L,x,y;
	cin >> N >> K >> L;
	init_train(N);init_way(N);
	while(K--){
		cin >> x >> y;
		unite_way(x,y);
	}
	while(L--){
		cin >> x >> y;
		unite_train(x,y);
	}
	for(ll i=1;i<=N;i++){
		ll ans=0;
		for(ll j=1;j<=N;j++){
			if(same_train(i,j)&&same_way(i,j))	ans++;
		}
		cout << ans;
		if(i!=N)	cout << ' ';
	}
	cout << endl;
	return 0;
}

Submission Info

Judge Result