Submission #1173674

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
typedef long long ll;

int n, m;
int par[100005], ran[100005], num[100005];

void init(int n) {
	FOR(i, n) {
		par[i] = i;
		ran[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 (ran[x] < ran[y]) par[x] = y;
	else {
		par[y] = x;
		if (ran[x] == ran[y]) ran[x]++;
	}
}

bool same(int x, int y) {
	return find(x) == find(y);
}

int main(int argc, char const *argv[]) {
	cin >> n >> m;
	init(n);
	FOR(i, m) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		unite(a, b);
	}

	FOR(i, n) {
		num[find(i)]++;
	}
	
	int ans = -1;
	FOR(i, n) {
		if (num[i]) ans++;
	}

	cout << ans << endl;

	return 0;
}

Submission Info

Judge Result