[백준]11724 연결 요소의 개수 - C/C++

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

11724번: 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

---

Union-Find 기법을 사용하여 문제를 풀어 같은 set 에 속해 있는지 구하면 되는 문제이다. 이때 path compression 기법을 사용하면 더욱 빠르게 문제를 풀 수 있다. 마지막에 연결요소의 개수를 확인 할 때 Find 함수를 이용하여 root노드를 구하고 std::find 함수를 이용하여 새로운 root 노드들만 추가하여 개수를 확인한다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int N, M,cnt;
int parent[1001] = { 0 };
vector<int>connected;
int Find(int a) {
	if (parent[a] == a)
		return a;
	return parent[a] = Find(parent[a]);
}

void Union(int a, int b) {
	parent[a] = parent[b];
	return ;
}
int main() {
	cin >> N >> M;
	for (int i = 0; i <= N; i++) {
		parent[i] = i;
	}
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		int x = Find(a);
		int y = Find(b);
		if (x != y) {
			Union(x, y);
		}
	}
	for (int i = 1; i <= N; i++) {
		int tmp = Find(i);
		if (find(connected.begin(), connected.end(), tmp) == connected.end()) {
			connected.push_back(tmp);
			cnt++;
		}
	}
	cout << cnt;
	return 0;
}

---

오늘은 공부가 너무 하기 싫어서 계절학기 선형대수학 복습도 안했다. 원래는 그 당일에 복습을 하지 않으면 다음 수업을 따라가지 못할까봐 복습을 했는데 주말을 끼니깐 내일 해도 되지 않을까 하는 안도감때문인지 너무 하기가 싫었다. 그래도 일주일 열심히 수업들었으니깐 오늘은 코딩만 하자하고 문제를 골랐는데 그 문제도 vector를 사용하려다가 잘 풀리지 않아 접고 쉬었다. 그리고 결국 다시 앉아서 다른 문제를 풀려고 문제를 찾던 중 4년전에 틀렸습니다로 남겨진 문제를 발견했다. 어떤 문제인지 궁금해서 들어갔는데 그래프의 연결요소 문제였다! 바로 union-find로 문제를 풀고 4년전에는 어떤 시도를 했을지 구경을 갔는데 방학때 시도를 한 것인지 엉성하게 vector를 쓰려고 했더라. 그때는 union find 를 모르고 adjacent matrix와 visited를 이용하여 풀려고 했던데 확실히 알고리즘 유형을 많이 보아야 문제도 빠르고 간결하게 풀 수 있는것 같다!