[백준] 1976 여행 가자 c++

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

1976번: 여행 가자

 

풀이과정

1이면 도시들이 연결된 것을 의미하므로 unionParent(i, j) 함수를 실행시켜준다.  
그럼 연결된 도시들은 가장 작은 부모 노드를 가지고 있을 것이다.  
여행 계획에 있는 도시들을 두 개씩 findParent에 넣어보고 만약에 다른 것이 있다면  
연결되지 않은 도시라는 뜻이므로 res를 false로 변경한다.

 

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

int N, M;
int parent[201], travel[1001];
bool res = true;

// 부모 노드를 찾는 함수
int getParent(int x) {
	if (parent[x] == x) return x;
	return parent[x] = getParent(parent[x]);
}

// 두 부모 노드를 작은 것으로 합치는 함수
void unionParent(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if (a > b) parent[a] = b;
	else parent[b] = a;
}

// 부모 노드가 같은지 확인하는 함수
void findParent(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if (a != b) res = false;
}

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

	cin >> N >> M;
	for (int i = 1; i <= N;i++) {
		parent[i] = i;
	}

	int num;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> num;
			if (num == 1) unionParent(i, j);
		}
	}
	for (int i = 0; i < M; i++) {
		cin >> travel[i];
	}
	for(int i = 0; i < M - 1; i++){
		findParent(travel[i], travel[i + 1]);
	}
	if (res) cout << "YES";
	else cout << "NO";
}