Submission #10472885

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 100010;
int A[MAX_N], B[MAX_N], C[MAX_N], D[MAX_N];
int parent[MAX_N];
int size[MAX_N];

int find_parent(int u) {
	if(parent[u] == -1) return u;
	return parent[u] = find_parent(parent[u]);
}

void merge(int u, int v) {
	u = find_parent(u);
	v = find_parent(v);
	if(u == v) return;
	parent[v] = u;
	size[u] += size[v];
}

void run() {
	int n, m, k, i;
	cin >> n >> m >> k;
	for(i=0; i<MAX_N; i++) {
		A[i] = B[i] = C[i] = D[i] = -1;
		parent[i] = -1;
		size[i] = 1;
	}
	for(i=0; i<m; i++) {
		cin >> A[i] >> B[i];
		--A[i]; --B[i];
		merge(A[i], B[i]);
	}
	for(i=0; i<k; i++) {
		cin >> C[i] >> D[i];
		--C[i]; --D[i];
	}
	vector<int> ret(n, 0);
	
	for(i=0; i<n; i++)
		ret[i] = size[find_parent(i)] - 1;

	for(i=0; i<m; i++) {
		--ret[A[i]];
		--ret[B[i]];
	}
	for(i=0; i<k; i++) {
		if(find_parent(C[i]) == find_parent(D[i])) {
			--ret[C[i]];
			--ret[D[i]];
		}
	}
	for(i=0; i<n; i++)
		cout << ret[i] << " ";
	cout << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);		
	int t = 1;
	// cin >> t;
	while(t--) {
		run();
	}
}

Submission Info

Judge Result