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

분리집합으로 풀리는 문제이다. 

미리 구현해둔 분리집합 알고리즘으로 쉽게 풀었다.

 

#include <bits/stdc++.h> 
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 987654321
typedef long long ll;
using namespace std;


int N, M;
int parent[1002];
//현재에는 자기 자신이 root임 

int find(int a) {
	//a가 root임
	if (parent[a] < 0) return a;
	//a가 root가 아닐때 
	return parent[a] = find(parent[a]);
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);

	if (a == b)return;
	//small to large
	if (parent[a] > parent[b]) swap(a, b);
	parent[a] += parent[b];
	parent[b] = a;
}

int main() {
	FASTIO;
	int a; 
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		parent[i] = -1;  //자기 자신이 parent이다.
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++){
			cin >> a;
			if (a == 1) {
				merge(i, j);
			}

		} 
	}
	int tmp;
	for (int i = 0; i < M; i++) {
		cin >> a;
		if (i == 0) {
			tmp = find(a);
		}
		else {
			if (tmp != find(a)) {
				cout << "NO";
				return 0;
			}
		}

	}
	cout << "YES";
}