백준 여행가자

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

1976번: 여행 가자

음 union find로 풀면 일단 경로는 잡을수 잇는데

가장 중요포인트는 이 경로가 전부 하나로 이어져잇는지에 대한 이해가 좀 필요한 문제입니다.

즉 경로들

경로0 1 2 3

루트0 2 3 3 일떄

1->2

2->3

3->3

이면 start가 1일 때 2로 가고 find를 통해 2에서 3으로 갑니다.

즉 다음 명령어인 2를 가도 동일 3으로 갑니다.

그리고 마지막 명령어인 3은 3루트를 가지고 잇으므로  3으로 갑니다.

이때 모든 명령어가 3루트라는곳을 향해 가기때문에 이 길들은 모두 하나로 이어져잇는셈이죠

import java.util.*;

import java.lang.*;
import java.lang.reflect.Array;
import java.io.*;
public class Main {

	private int  parent[];
	public Main(int size) {
		parent =new int[size];
		
		for(int i=0;i<size;i++) {
			parent[i]=i;
		}
	}
	
    public int find(int x) {
    	if(x!=parent[x]) {
    		parent[x]=find(parent[x]);
    	}
    	return parent[x];
    }
    
    public int track(int x) {
    	if(x!=parent[x]) {
    		parent[x]=find(parent[x]);
    	}
    	return parent[x];
    }
    
	public void union(int x,int y) {
		int rootX=find(x);
		int rootY=find(y);
		
		if(rootX!=rootY) {
			parent[rootX]=rootY;
		}
	}
	public void Prints(int size ) {
		for(int i=0;i<size;i++) {
		   System.out.print(parent[i]+",");
		}
	}
	
	public static void main(String[] args) throws Exception {
		Scanner scan =new Scanner(System.in);
        //동혁이는 친구들과 함꼐 여향을 가려한다.
		// 한국에는  도시가 n개 잇고
		//임의의 두 도시 사이에 길이 잇을수도 잇고 없을수도 잇다 
		//동혁이는 여행 일정이 주어졋을때,
		//이 여행 경로가 가능한것인지 확인
		//물론 중간에 다른 도시를 경유해서 여행할수 잇다
		//예를들어  a-b, b-c, a-d, b-d, e-a
		// e  c  b c d 
		// E-A-B-C-B-C-B-D
		//길의 가능여부를 판별 하는것을 작성하자 
		int n=scan.nextInt();
		int m=scan.nextInt();
		
		Main uf=new Main(n+1);
		for(int i=1;i<n+1;i++) {
			for(int j=1;j<n+1;j++) {
			int a=scan.nextInt();
			
				//if(i!=j) {
					if(a==1) {
						uf.union(i, j);
					}
					
				//}
			
			}			
		}
		
		boolean bCheck=false;
		int start=uf.find(scan.nextInt());
		for(int i=1;i<m;i++) {
			if(start!=uf.find(scan.nextInt()))
			{
				bCheck=true;
				break;
			}
		}
		
		if(bCheck==false) {
			System.out.println("YES");
		}else {
			System.out.println("NO");
		}
		
	}
}