Submission #310878

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <numeric>
#define FOR(x, to) for (int x = 0; x < to; x++)

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

int ans;
int N, M;
int parent[100005];

void init() {
	for (int i = 0; i < 100005; i++) {
		parent[i] = i;
	}
}

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

void unite(int x, int y) {
	int a = find(x);
	int b = find(y);
	if (a == b) return;
	parent[b] = a;
}


int main() {
	cin >> N >> M;
	init();
	FOR(i, M) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		//cout << a << " " << b << endl;
		unite(a, b);
	}
	FOR(i, N) {
		int x = find(i);
		if (i == x) ans++;
	}
	cout << ans-1 << endl;
	return 0;
}

Submission Info

Judge Result