[백준 1976] 여행 가자

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

1976번: 여행 가자

요구 사항

1. Union-Find 구현

 

풀이

1. 여행 경로가 주어졌을 때, 모든 여행지의 대표값이 동일한지 확인

 

#include <iostream>

using namespace std;

int parent[1000001];
int map[1001][1001];
int n, m;
int p[1001];
int Find(int x)
{
	if (parent[x] == x)
		return x;
	else
		return parent[x] = Find(parent[x]);
}
void Union(int x, int y)
{
	x = Find(x);
	y = Find(y);
	if (x != y)
	{
		if (x < y)
			parent[y] = x;
		else
			parent[x] = y;
	}

}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	int x, y, z;
	for (int i = 0; i <= n; i++)
		parent[i] = i;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 1)
				Union(i, j);
		}
	}
	for (int i = 0; i < m; i++)
	{
		cin >> p[i];
	}

	for (int i = 0; i < m - 1; i++)
	{
		if (Find(p[i]) != Find(p[i + 1]))
		{
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
	return 0;
}