(코테) 백준_20040_사이클 게임 *유니온 파인드

 

 

 

 

package codingTest;
import java.util.*;
import java.io.*;

public class Backjun_20040 {
	static int N,M;
	static int[] parents;
	static int count = 0;
	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());
		M = Integer.parseInt(st.nextToken());		
		parents =new int[N];
		for(int i=0;i<N;i++){
			parents[i]=i;
		}
		
		for(int i=0; i<M; i++){
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());			
			if(find(x)==find(y)){
				count=i+1;
				break;	
			}else{
				union(x,y);
			}
		}
		System.out.print(count);		
	}
	
	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) {
			if(a<b){
				parents[b] =a;	
			}else{
				parents[a] =b;
			}				
		}
	}
}