[백준 1976] 여행 가자

 

유니온파인드 문제이다.

 

두 도시의 연결정보가 주어지면 union 연산을 한다.

여행계획이 주어졌을때 매 도시마다 find 연산을 하여 루트가 모두 같으면 YES 하나라도 다르면 NO를 출력한다.

 

public class Main {
    
    static int a[];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        
        a = new int[n];
        Arrays.fill(a, -1);
        
        st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                int c = Integer.parseInt(st.nextToken());
                if(c == 1) union(i, j);
            }
        }
        
        st = new StringTokenizer(br.readLine());
        int result = find(Integer.parseInt(st.nextToken()) - 1);
        for(int i=0; i<m-1; i++) {
            if(find(Integer.parseInt(st.nextToken()) - 1) != result) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }
    
    public static int find(int n) {
        if(a[n] < 0) return n;
        a[n] = find(a[n]);
        return a[n];
    }
    
    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if(x == y) return;
        a[x] += a[y];
        a[y] = x;
    }
}