Submission #1218575

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define INF 2000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> P;

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

int main()
{
	int n,m;
	cin >> n >> m;
	struct UnionFind u(n+1);

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		u.unionSet(a,b);
	}

	set<int> st;
	for (int i = 1; i <= n; i++) {
		int r = u.root(i);
		st.insert(r);
	}

	cout << st.size()-1 << "\n";
}

//N M
//a1 b1
//a2 b2
//:
//aM bM

Submission Info

Judge Result