[백준OJ] 11724번 연결 요소의 개수

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

11724번: 연결 요소의 개수

---

 

-풀이-

UNION&FIND 알고리즘을 이용하여, 입력받은 간선들을 이용하여 자신의 최고 조상을 설정한다.

그런뒤 마지막으로, 최고조상의 개수만 세어주면, 연결요소의 개수를 셀 수 있다.

 

-시간-

Union Find 함수는 O(LogN)시간이 걸리는데, 초기화는 O(N)시간이 걸리므로, 총 O(N)이 된다.

 

-코드-

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int parent[1001];

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

void union_parent(int a, int b) {
	a = find(a);
	b = find(b);

	if (a < b) {
		parent[b] = a;
	}
	else {
		parent[a] = b;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		union_parent(a, b);
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (i == parent[i]) {
			cnt++;
		}
	}
	cout << cnt << "\n";
	return 0;
}