[백준]Baekjoon2606(유니온 파인드)

문제링크 : https://www.acmicpc.net/problem/2606

풀이

같은 집합에 대해서 하나로 묶어주고 찾고자 하는것이 해당 집합에 포함되어 있는지 찾을 수 

있는 유니온파인드 자료구조를 사용하였다.

자세한 방식에 대해서는 http://dolphins-it.tistory.com/223 를 참조하자.

#include <iostream>

using namespace std;

int computer[101];

int find(int x)
{
	if (x == computer[x]) return x;
	else {
		int y = find(computer[x]);
		computer[x] = y;
		return y;
	}
}
void merge(int x, int y)
{
	int a = find(x);
	int b = find(y);
	computer[b] = a;
}
int main()
{
	int n;
	int con;
	scanf("%d %d", &n, &con);
	for (int i = 0; i <= n; i++) computer[i] = i;

	while (con--)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		merge(x, y);
	}
	int root = find(1);
	int answer = 0;
	for (int i = 0; i <= n; i++) {
		if (find(i) == root)
			answer++;
	}
	printf("%d\n", answer-1);
}