[백준] 1976번 여행 가자

문제 출처: https://www.acmicpc.net/problem/1976

1976번: 여행 가자

여행 계획에 포함되어 있는 도시들은 출발 도시와 연결된(같은 집합인) 도시이기만 하면 도착할 수 있다. 따라서 연결된 도시에 대해 merge()를 한 뒤 여행계획에 포함된 모든 도시들이 같은 집합에 포함되어 있는지 확인하여 답을 구할 수 있다.

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

int U[201];

int find(int a) {
	if (U[a] < 0)return a;
	return U[a] = find(U[a]);
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)return;
	if (U[a] < U[b]) {
		U[a] += U[b];
		U[b] = a;
	}
	else {
		U[b] += U[a];
		U[a] = b;
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	fill(&U[0], &U[201], -1);
	int n;
	cin >> n;
	int m;
	cin >> m;

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

	int prev;

	for (int i = 0; i < m; i++) {
		int temp;
		cin >> temp;

		if (i == 0) {
			prev = find(temp);
		}
		else {
			if (prev != find(temp)) {
				cout << "NO";
				return 0;
			}
		}
	}

	cout << "YES";
	
}