[BOJ 24391 // C++] 귀찮은 해강이

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 24391번 문제인 귀찮은 해강이이다.

문제는 아래 링크를 확인하자.

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

24391번: 귀찮은 해강이

서로 연결되어있는 건물들을 하나의 집합에 묶고, 이전에 강의를 들은 건물이 속한 집합과 다음에 강의를 들을 건물이 속한 집합이 서로 다른지 판단하는 것으로 문제를 해결할 수 있다.

 

이와 같은 연산은 disjoint set 자료구조를 이용하여 쉽게 처리할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int uf[100001];
int findf(int x) {
	if (uf[x] == x) return x;
	return uf[x] = findf(uf[x]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M; cin >> N >> M;
	for (int i = 1; i <= N; i++) uf[i] = i;

	while (M--) {
		int x, y; cin >> x >> y;
		x = findf(x), y = findf(y);
		uf[y] = x;
	}

	int cnt = 0;
	int current; cin >> current;
	current = findf(current);
	for (int i = 1; i < N; i++) {
		int x; cin >> x;
		x = findf(x);
		if (x != current) {
			cnt++;
			current = x;
		}
	}

	cout << cnt;
}