[백준 1976] 여행 가자

문제 : 여행 가자

Union Find (Disjoins set) 알고리즘으로 풀 수 있는 문제다.

문제 풀이 과정은 다음과 같다.

1. 도시의 수, 여행 계획에 속한 도시의 수를 입력받은 뒤, 도시들 사이의 연결관계를 나타낸 입력을 받는다.
2. 입력을 받으면서 동시에 Union을 진행한다.
3. 여행 계획에 속한 도시를 전부 순회하며 여행 계획의 첫 번째 도시와 find 값을 비교한 뒤 하나라도 find값이 다를 경우 NO, 정상적으로 반복문을 수행하였으면 YES를 출력한다.

#include <iostream>
#include <vector>

int		n, m;
int		arr[201];
int		travel[1000];

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

void	uni(int a, int b)
{
	a = find(a);
	b = find(b);
	if (a == b)
		return ;
	arr[a] = b;
}

int 	main(void)
{
	int		i, j;
	int		temp;
	
	scanf("%d", &n);
	scanf("%d", &m);
	i = 1;
	while (i <= n)
	{
		arr[i] = i;
		i++;
	}
	i = 1;
	while (i <= n)
	{
		j = 1;
		while (j <= n)
		{
			scanf("%d", &temp);
			if (temp == 1)
				uni(i, j);
			j++;
		}
		i++;
	}
	i = 0;
	while (i < m)
	{
		scanf("%d", &travel[i]);
		i++;
	}
	i = 0;
	while (i < m)
	{
		if (find(travel[0]) != find(travel[i]))
		{
			printf("NO\n");
			return 0;
		}
		i++;
	}
	printf("YES\n");
	return (0);
}