백준 2606 : 바이러스

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

2606번: 바이러스

 

그래프에서 연결성을 확인하는 문제로, 유니온-파인드 알고리즘으로 풀 수 있다.

유니온 파인드 알고리즘은 재귀적으로 부모 정보를 갱신하고 최상단 부모노드를 리턴하는 파인드 함수와 부모가 다를 시 한 노드가 다른 한 노드의 부모가 되도록하는 유니온 함수로 이루어져 있다.

 

#include <iostream>

using namespace std;

int parent[101];

//파인드
int ffind(int x) {
	//parent[x] == x일 시 부모가 없으므로 자기 자신 리턴
	if (parent[x] == x) return x;
    //아닐 시, 재귀적으로 올라가면서 부모 노드를 최상단 부모노드로 갱신 하고 리턴
	else return parent[x] = ffind(parent[x]);
}

//유니온
bool funion(int x, int y) {
	x = ffind(x);
	y = ffind(y);

	//x와 y의 최상단 부모가 같지 않을 시 union 수행
	if (x != y) {
    	//노드 번호가 더 작은 쪽이 부모가 되도록 swap
		if (x > y) {
			int tmp = x;
			x = y;
			y = tmp;
		}

		parent[y] = x;
		return 1;
	}

	return 0;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, m; cin >> n >> m;
	int a, b;
	int cnt = 0;

	//parent 배열을 자기 자신의 idx값으로 초기화
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}

	while (m--) {
		cin >> a >> b;
		funion(a, b);
	}

	//최상단 부모 노드가 1인 경우 갯수 체크
	for (int i = 1; i <= n; i++) {
		if (ffind(i) == 1) cnt++;
	}

	cout << cnt - 1;

	return 0;
}

메모리: 2020 kb

시간: 0 ms