Boj1976_여행가자

Published: December 04, 2018 by 아형

• Categories:
• Algorithm 74

• Tags:
• 알고리즘 72

boj1976_여행가자

• union find의 집합의 갯수, level 등은 상관 안해줘도 되는 문제!

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

int n, m,num;
vector<int> p;
int getParent(int a) {
	return p[a] == a ? p[a] : p[a]=getParent(p[a]);
}
void merge(int a, int b) {
	int ap = getParent(a);
	int bp = getParent(b);
	p[bp] = ap;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i <= n; i++) {
		p.push_back(i);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &num);
			if (num && getParent(i)!=getParent(j)) {
				merge(i, j);
			}
		}
	}
	int temp = 0,ans=1; 
	for (int i = 0; i < m; i++) {
		scanf("%d", &num);
		if(i==0) temp = getParent(num);
		if (temp != getParent(num)) ans = 0;
	}
	if (ans == 1) printf("YES");
	else printf("NO");
}