[BOJ] #1976 _ 여행 가자

[여행가자] https://www.acmicpc.net/problem/1976

1976번: 여행 가자

문제의 ABCDE의 연결 상태를 그래프로 나타내면 다음과 같다.

 

그래프를 보면, 모두 연결되어 있으며 최상위 부모 노드가 A로 동일하다.

따라서, 도시간에 연결되어 있는지 알기 위해서는 최상위 부모노드가 동일한지 판단하면 된다.

 

[ 소스 코드 ]

#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX 201

using namespace std;

int N, M;
int chk[MAX], map[MAX][MAX], tour[1000];

int findParent(int idx);
int solve();
int main() {
	scanf("%d\n%d", &N, &M);
	for (int i = 1; i <= N; i++) chk[i] = i;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	for (int i = 0; i < M; i++) scanf("%d", &tour[i]);

	int tmp_1, tmp_2;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j]) {
				tmp_1 = findParent(i);
				tmp_2 = findParent(j);

				if (tmp_1 < tmp_2) chk[chk[j]] = tmp_1;
				else if (tmp_1 > tmp_2) chk[chk[i]] = tmp_2;
			}
		}
	}

	if (solve()) printf("YES\n");
	else printf("NO\n");

	return 0;
}

int findParent(int idx) {
	while (1) {
		if (idx == chk[idx]) return idx;
		idx = chk[idx];
	}
}

int solve() {
	int cmp = findParent(tour[0]);
	for (int i = 1; i < M; i++) {
		if (cmp != findParent(tour[i])) return 0;
	}

	return 1;
}