[BOJ] 백준 1976 여행 가자

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

 Input 

3

3

0 1 0

1 0 1

0 1 0

1 2 3

 

 Output 

 YES

※ Disjoint-Set & Union-Find 

Disjoint-Set & Union-Find

무방향 그래프로  Aij = Aji이므로 i > j 인 경우만 union 연산

Union-Find 구현 후, 주어진 정점들이 가리키는 부모노드가 모두 같은지 확인

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    static int[] parent;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
         
        int N = Integer.parseInt(br.readLine());
        int 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++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++) {
                int val = Integer.parseInt(st.nextToken()); 
                if(i > j && val == 1) {
                    union(i, j);
                }
            }
        }
         
        int[] arr = new int[M];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++) {
            // 방문할 정점 입력
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for(int i=1; i<arr.length; i++) {
            // 하나라도 소속 그래프가 다른 경우
            if(find(arr[i-1]) != find(arr[i])) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
}
     
    private static void union(int a, int b) {
        a = find(a); b = find(b);       
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }
 
    private static int find(int x) {
        if (x == parent[x])
            return x;
        return parent[x] = find(parent[x]);
    }
}