[BOJ]백준 1976번: 여행 가자/Union Find

www.acmicpc.net/problem/1976

1976번: 여행 가자

유니온 파인드(Disjoint Set)을 활용해서 정점간의 연결을 확인하는 문제이당

도시의 연결 정보가 주어질 때 마다 Union 연산을 한 뒤, 여행 계획에 속한 정점들이 같은 Parent에 속해있는지 확인하면 된다

 

#include <cstdio>
#include <vector>
using namespace std;
struct disjointSet {
	vector<int> parent, rank;

	disjointSet(int n) {
		rank.resize(n + 1);
		for (int i = 0; i <= n; i++)
			parent.push_back(i);
	}

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

	void unionSet(int u, int v) {
		u = find(u); v = find(v);
		int temp;

		if (u == v)return;
		if (rank[u] > rank[v]) { temp = u; u = v; v = temp; }
		parent[u] = v;
		if (rank[u] == rank[v])++rank[v];
	}
};
int n,m,p;
int main() {
	scanf("%d%d", &n,&m);
	disjointSet d(n);

	for(int i=1;i<=n;i++)
		for (int j = 1,k; j <= n; j++) {
			scanf("%d", &k);
			if (!k)continue;
			if (d.find(i) != d.find(j))
				d.unionSet(i, j);
		}
	scanf("%d", &p); p = d.find(p);
	for (int i = 0,k; i < m-1; i++) {
		scanf("%d", &k);
		if (d.find(k) != p) { printf("NO"); return 0; }
	}
	printf("YES");
	return 0;
}