algorithms 백준 (BOJ)

[BOJ]백준 1976번: 여행 가자 (baekjoon 1976)

2020.02.25 ·

(BOJ)백준 1976 - 1976번: 여행 가자

1976번: 여행 가자

[BOJ] 백준 (1976)

백준 1976 - 1976번: 여행 가자

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

코드

import java.io.*;
import java.util.Arrays;

public class B1976 {
    static int n, m, p[] = new int[201];
    static String ins[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        Arrays.fill(p, -1);
        for (int i = 0; i < n; i++) {
            ins = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                if (ins[j].equals("1")) union(i, j);
            }
        }
        ins = br.readLine().split(" ");
        boolean flag = true;
        int root = find(Integer.parseInt(ins[0]) - 1);
        for (int i = 1; i < m; i++) {
            if (root != find(Integer.parseInt(ins[i]) - 1)) {
                flag = false;break;
            }
        }
        bw.write((flag ? "YES\n" : "NO\n"));
        bw.flush();bw.close();
    }

    public static int find(int n) {
        if (p[n] < 0) return n;
        p[n] = find(p[n]);
        return p[n];
    }
    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        p[b] = a;
    }
}

설명