[java 백준] 20040번 사이클게임

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

20040번: 사이클 게임

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
class Main {
 
    public static int n;
    public static int m;
 
    public static int []parents;
 
    public static int find(int a){
        if(parents[a]!=a){
            parents[a]=find(parents[a]); //끝까지 부모를 찾아낸다.
        }
 
        return parents[a]; //이게 중요! 왜??
        //만약에 a는 2이고 parents[a]=1일 때
        //2의 부모는 1이 맞음
        //그렇기에 a가 2일때 부모인 1을 뱉어내야함
    }
 
    public static void union(int a,int b){
        a=find(a);
        b=find(b);
 
        if(a<b){
            parents[b]=a;
        }
        else{
            parents[a]=b;
        }
    }
 
 
 
    
 
 
 
 
 
 
    public static void main(String args[]) throws NumberFormatException, IOException {
 
       BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st;
       st=new StringTokenizer(br.readLine());
       n=Integer.parseInt(st.nextToken());
       m=Integer.parseInt(st.nextToken());
       
       //여행 계획에 있는 도시들의 부모가 다 같으면 됨
 
        parents=new int[n+1];
 
        for(int i=0;i<n;i++){
            parents[i]=i;
        }
 
 
       for(int i=0;i<m;i++){
           st=new StringTokenizer(br.readLine());
           int a=Integer.parseInt(st.nextToken());
           int b=Integer.parseInt(st.nextToken());
           if(find(a)==find(b)){
               System.out.println(i+1);
               return;
           }else{
               union(a,b);
           }
       }
 
 
       System.out.println(0);
 
 
      
 
 
 
 
 
 
 
    }
 
}

 

이 문제는 유니온 파인드로 푸는 문제였다. 결국에 사이클이 발생하는 경우는 같은 집합인 경우고 부모노드가 같은 애들이기 때문이다! 하지만 이 부모가 같은걸 판단하는 시점이 언젠지 파악하는게 중요 했다. 우선 find를 통해 부모가 같은지 판단을 하고 같으면 종료, 부모가 다른 경우 union을 시켜주는 거였다. 

 

즉, union하기 전에 부모가 같아야 사이클이 발생하는 거였다!!