[BJ] 1976 : 여행가자 - unsolved

       문제 요약        

- 문제

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

 

         아이디어        

 

 

- 유니온 파인드

처음 배열 초기화의 의미 : 모든 노드가 자기 자신을 부모로 갖도록 한다. 그럼으로써 모든 노드가 독립적인 집합에 속합을 나타낸다 

         소스코드        

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int M;
	static int[] parent;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		parent = new int[N + 1];
		for (int i = 1; i <= N; i++) { // 모든 노드가 자기 자신을 부모로 가지도록 설정
			parent[i] = i; // 모든 노드가 독립적인 집합에 속해 있음을 나타냄
		}
		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				int isConnected = Integer.parseInt(st.nextToken());
				if (isConnected == 1) {
					union(i, j);
				}
			}
		}

		StringTokenizer st = new StringTokenizer(br.readLine());
		int start = find(Integer.parseInt(st.nextToken()));
		for (int i = 1; i < M; i++) {
			int now = Integer.parseInt(st.nextToken());
			if (start != find(now)) {
				System.out.println("NO");
				return;
			}
		}
		System.out.println("YES");

	}

	static void union(int i, int j) {
		i = find(i);
		j = find(j);
		if (i != j) {
			if (i > j)
				parent[i] = j;
			else
				parent[j] = i;
		}
	}

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