백준 1976번: 여행 가자

 

 

 

 

 

Union-find를 활용한 문제이므로 각 도시들이 연결되었는지 확인 하려면 root가 같은지만 확인하면 된다.

root가 같으면 다른 도시들을 거쳐서라도 갈수 있기 때문.

 

 

 

*** Union-find 개념 ***

https://gimmesome.tistory.com/34?category=1103655

[1주차] Union-find

 

 

 

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

int N, M;
int arr[200];

int findParent(int num) {
	if (arr[num] < 0)
		return num;
	int parent = findParent(arr[num]);
	arr[num] = parent;
	return parent;
}

void merge(int iParent, int jParent) {
	if (abs(arr[iParent]) >= abs(arr[jParent])) {
		arr[iParent] += arr[jParent];
		arr[jParent] = iParent;
	}
	else {
		arr[jParent] += arr[iParent];
		arr[iParent] = jParent;
	}
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상

	cin >> N >> M;

	for (int i = 0; i <= N; i++) {
		arr[i] = -1;
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {

			int connected;
			cin >> connected;

			if (connected) {
				int iParent = findParent(i);
				int jParent = findParent(j);

				if (iParent == jParent)
					continue;
				merge(iParent, jParent);
			}
		}
	}

	int root;
	bool possible = true;
	for (int i = 0; i < M; i++) {
		int city;
		cin >> city;

		//첫 도시에서 root를 구해놔야 나중에 비교할게 있음
		if(i == 0)
			root = findParent(city-1); 
		else {
			if (root != findParent(city-1)) {
				possible = false;
				break;
			}
		}
	}

	if (possible) 
		cout << "YES\n";
	else
		cout << "NO\n";

	return 0;
}