(코테) 백준_1976_여행 가자 *유니온 파인드

 

 

 

 

 

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


/*

3
3
0 1 0
1 0 1
0 1 0
1 2 3
 
*/

public class Main {
	static int N,M;
	static int[] parents;
	static int[][] map;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		parents = new int[N+1];
		map = new int[N+1][N+1];
		
		for(int i=1;i<N+1;i++) {
			parents[i] =i;			
		}
		
		for(int i=1;i<N+1;i++) { // 여행지
			st = new StringTokenizer(br.readLine());
			for(int j =1;j<N+1;j++) {				
				map[i][j] =  Integer.parseInt(st.nextToken());
				if(map[i][j]==1) { //연결된 여행지임 1
					union(i,j);					
				}
			}
		}
		
		st = new StringTokenizer(br.readLine());
		
		int reffere =Integer.parseInt(st.nextToken());
		boolean flag = false;
		
		for(int i=1;i<M;i++) {  //여행 계획
			int now=Integer.parseInt(st.nextToken());

			if((find(reffere)!=find(now))) {
				flag = true;
				break;	
			}
			reffere = now; //최신화
		}		
		
		if(flag) System.out.print("NO");
		else System.out.print("YES");
	}
	public static int find(int num) {
		if(parents[num]==num) return num;   //루트값인지?
		else return parents[num] = find(parents[num]);//아니라면 최상위 부모 찾기

	}

	public static void union(int x , int y) {
		int a=find(x); //루트 찾기
		int b=find(y); //루트 찾기 
         if (a != b) { //값이 동일하면 pass
          if (a < b) parents[b] = a;  ////최상위 루트(부모) 설정 (작은 값이 부모로)
          else parents[a] = b; 
        }
	}
}