Submission #1301603

---

Source Code Expand

#include<cstdio>
#include <iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1000000007;

int N, M;
int par[100010], rk[100010];

void init(int n) {
	for (int i = 1; i <= n; i++) {
		par[i] = i;
		rk[i] = 0;
	}
}

int find(int x) {
	if (par[x] == x)return x;
	else
		return par[x] = find(par[x]);
}

void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)return;

	if (rk[x] < rk[y])
		par[x] = y;
	else {
		par[y] = x;
		if (rk[x] == rk[y])rk[x]++;
	}
}

int main() {
	cin >> N >> M;

	init(N);
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		a, b;
		unite(a, b);
	}
	
	set<int> s;
	for (int i = 1; i <= N; i++) {
		s.insert(par[i]);
	}

	cout << s.size() - 1 << endl;
	return  0;
}

Submission Info

Judge Result