[백준] 2606: 바이러스 - C/C++

문제 출처

https://www.acmicpc.net/problem/2606

---

실버3 유니온 파인드 또는 dfs 문제이다.

 

dfs로 푸는 풀이는 경우가 많지만,

이 문제와 같은 경우는 1번 컴퓨터와 연결되어있는지 안되어있는지만 확인하면 되는 문제이므로

유니온 파인드를 이용한 풀이도 가능하다.

유니온 파인드에 관한 해설은 아래 링크를 참고하면 된다.

https://codingul1234.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C-Union-Find

[알고리즘] 유니온 파인드 (Union-Find)

 

#풀이

#include<iostream>
#define MAX 100
using namespace std;
int parent[MAX + 1] = { 0, };
int Find(int n) {
	if (parent[n] == n) return n;
	else return parent[n] = Find(parent[n]);
}

void Union(int x, int y) {
	x = Find(x);
	y = Find(y);
	
	if (x != y) {
		if (x < y) {
			parent[y] = x;
		}
		else {
			parent[x] = y;
		}
	}
}
int main()
{
	int N, M, ans = 0;
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		parent[i] = i;
	}

	for (int i = 0,a,b; i < M; i++) {
		cin >> a >> b;
		Union(a, b);
	}

	for (int i = 2; i <= N; i++) {
		if (Find(i) == 1) ans++;
	}

	cout << ans;
	return 0;
}