[백준(Baekjoon)][자바(java)] 20040 : 사이클 게임 / 유니온 파인드

 

www.acmicpc.net/problem/20040

20040번: 사이클 게임

 

문제 풀이

 

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

public class Main {
	
	public static int find( int x, int p[] ) {
		if( x == p[x] )  return x;
		return p[x] = find( p[x], p );
	}
	
	public static boolean union( int a, int b, int p[] ) {
		if( a == b )  return true;
		a = find( a, p );
		b = find( b, p );
		if( a == b )  return true;
		p[b] = a;
		return false;
	}
	
	public static void main(String[] args) throws IOException {
	
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		StringTokenizer st = new StringTokenizer( br.readLine() );
		int n = Integer.parseInt( st.nextToken() ), 
		    m = Integer.parseInt( st.nextToken() ), a, b, c = 0, i;
		int p[] = new int[n];
		boolean f = false;  // f -- isCycle
		for( i = 0; i < n; i++ )
			p[i] = i;
		for( i = 0; i < m; i++ ) {
			st = new StringTokenizer( br.readLine() );
			a = Integer.parseInt( st.nextToken() );
			b = Integer.parseInt( st.nextToken() );
			if( !f && union( a, b, p ) ) {
				f = true;
				c = i+1;
			}
		}
		br.close();
		System.out.println( c );
	}
}

 

*  유니온 파인드

-  간선 입력받을 때 두 정점을 union() 함
   이미 같은 집합 안에 있을 경우 사이클이므로 true 반환, 사이클이 아니면 false 반환
-  boolean f ( flag ) 변수로 사이클이 처음 나올 때를 체크
   사이클이 처음 등장하는 경우 f가 true가 되고, 몇 번째인지를 구해 출력