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

문제 링크: https://www.acmicpc.net/problem/1976

 

이 문제는 그래프가 주어졌을 때 M개의 점이 같은 컴포넌트에 있는지, 다른 컴포넌트로 분리되어 있는지 찾는 문제입니다.

그냥 그래프 탐색만 하면 되는 문제인데, 유니온 파인드를 복습하는 기분으로 풀어봤습니다.

 

먼저 도시가 입력될 때 0이 아니면 두 정점을 merge 합니다.

그리고 여행이 가능하다는 것은 도시가 같은 집합에 들어있는 얘기니까 여행할 도시들에 find를 해서 전부 같은지 확인해서 같으면 true, 아니면 false를 체크합니다.

 

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;


vector<vector<int>> graph;

vector<int> parent;

void init(int n) {
	parent.resize(n);
	for (int i = 0; i < n; ++i)
		parent[i] = i;
}

int find(int u) {
	if (u == parent[u]) return u;
	return parent[u] = find(parent[u]);
}

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;

	parent[u] = v;
}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, m;
	cin >> n >> m;

	init(n);
	graph = vector<vector<int>>(n, vector<int>(n));

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> graph[i][j];
			if (graph[i][j])
				merge(i, j);
		}
	}

	bool flag = true;
	
	int c;
	cin >> c;

	int city = find(c - 1);
	for (int i = 0; i < m - 1; ++i) {
		cin >> c;
		if (find(c - 1) != city) {
			flag = false;
		}
	}


	cout << (flag ? "YES\n" : "NO\n");
	

	return 0;
}