[BOJ] 1976 여행 가자(분리집합)

문제

www.acmicpc.net/problem/1976

1976번: 여행 가자

풀이

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

public class Main {
	static int N, M;
	static int[][] city;
	static int[] parent;
	static int[] trip;
	public static int find_parent(int num) {
		int tmp = num;
		while(tmp!=parent[tmp]) {
			tmp = parent[tmp];
		}
		return tmp;
	}
	public static void union(int n1, int n2) {
		int p1 = find_parent(n1);
		int p2 = find_parent(n2);
		
		if(p1<p2)
			parent[p2] = p1;
		else
			parent[p1] = p2;
	}
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		//선언 및 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());//도시 수
		M = Integer.parseInt(br.readLine());//여행 계획 도시 수
		parent = new int[N+1];
		city = new int[N+1][N+1];
		trip = new int[M+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++) {
				city[i][j] = Integer.parseInt(st.nextToken());
				if(city[i][j]==1)
					union(i,j);
			}
		}
		//여행 경로 입력
		st = new StringTokenizer(br.readLine());
		for(int i=1;i<=M;i++)
			trip[i] = Integer.parseInt(st.nextToken());
		
		//계산
		boolean chk = true;
		for(int i=1;i<M;i++) {
			if(find_parent(trip[i])!=find_parent(trip[i+1])) {
				chk = false;
				break;
			}
		}
		
		if(chk)
			System.out.println("YES");
		else
			System.out.println("NO");
	}

}