Submission #1610574

---

Source Code Expand

#include <iostream>
#include <vector>

using namespace std;

class up_tree {
public:
	int n;
	int *elem;

	up_tree(int x) {
		if (n>0) {
			n = x;
			elem = new int [x];
			for (int i=0; i<x; i++)
				elem[i] = -1;
		}
	}

	int set (int x) {
		if (elem[x] == -1) 
			return x;
		int ans = set(elem[x]);
		elem[x] = ans;
		return ans;
	}

	void combine(int x, int y) {
		if (set(x) == set(y))
			return;

		if (set(x) == x) {
			elem[x] = y;
			return;
		}

		if (set(y) == y) {
			elem[y] = x;
			return;
		}

		elem[set(x)] = y;
	}

	bool connected (int x, int y) {
		return (set(x) == set(y));
	}

};

int main () {

	int n, k, l;

	cin >> n >> k >> l;

	up_tree road (n);
	up_tree rail (n);

	for (int i=0; i<k; i++) {
		int x, y;
		cin >> x >> y;
		road.combine(x-1, y-1);
	}

	for (int i=0; i<l; i++) {
		int x, y;
		cin >> x >> y;
		rail.combine(x-1, y-1);
	}

	int total [n];
	bool done [n];
	for (int i=0; i<n; i++) {
		total[i] = 0;
		done[i] = false;
	}



	for (int i=0; i<n; i++) {
		if (done[i])
			continue;
		vector<int> both;
		both.push_back(i);
		for (int j=i+1; j<n; j++) {
			if (road.connected(i, j) && rail.connected(i, j)) {
				both.push_back(j);
				done[j] = true;
			}
		}
		for (int j: both) {
			total[j] += (int) both.size();
		}
	}

	for (int i=0; i<n-1; i++)
		cout << total[i] << " ";
	cout << total[n-1] << endl;



	return 0;
}

Submission Info

Judge Result