[BOJ/C++] 1976 여행 가자 : Union-Find

문제

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

풀이

Union-Find | 서로소 집합을 구하는 알고리즘
여러 노드가 존재할 때, 두개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 있는지의 여부를 판별하는 알고리즘

• Find 연산 : 노드 x가 어느 집합에 포합되어 있는지 찾는 연산
• Union 연산 : 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산
  
  

문제 풀이 방법
1. parent 배열 자기 자신으로 초기화
2. 그래프 연결 정보에 따라 Union 함수 호출해서 parent 배열 변경

3. Find 함수 호출해서 여행 경로에 있는 도시의 parent가 전부 같은지 확인
   3-1. 하나라도 다르면 "NO" 출력
   3-2. 전부 같으면 "YES" 출력
   
   

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> parent;

int Find(int x) {
	if (parent[x] == x)	return x;
	return parent[x] = Find(parent[x]);
}

void Union(int a, int b) {
	int x = Find(a); //root 찾기
	int y = Find(b);
	
	if (x < y)	parent[y] = x;
	else {
		parent[x] = y;
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n >> m;
	for (int i = 0; i <= n; i++) {
		parent.push_back(i);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int tmp;
			cin >> tmp;
			if (tmp) {
				Union(i, j);
			}
		}
	}

	int root;
	for (int i = 0; i < m; i++) {
		int tmp;
		cin >> tmp;
		if (i == 0)	root = Find(tmp);
		else {
			if (Find(root) != Find(tmp)) {
				cout << "NO";
				return 0;
			}
		}
	}
	cout << "YES";

	return 0;
}