백준 20040 <사이클 게임>

이 문제는 누구 순서인지는 고려할 필요가 없는 단순히 지금까지 그린 선분이 사이클이 이뤄진 것인지 판단하는 문제이다.

 

이 문제를 다르게 생각하면 하나의 집합인가? 로 보면 되겠다. 그러면 이 문제는 union-find 문제이다.

 

자기 자신이 부모일 때까지 재귀를 돌려주고 최상위 부모로 전체를 세팅한다.

 

알고리즘을 많이 아는 것이 좋다는 점을 이런 문제를 보고 깨닫는다.!

 

전체 코드 

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

public class Main {

	static int p[],n,m,result;
	public static void main(String[] args) throws NumberFormatException, 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());
		p=new int[n+1];
		for(int i=0;i<=n;i++) {
			p[i]=i;
		}
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int f=Integer.parseInt(st.nextToken());
			int s=Integer.parseInt(st.nextToken());
			int p1=findp(f);
			int p2=findp(s);
			if(p1==p2) {
				result=i+1;
				break;
			}
			p[p1]=p2;
		}
		System.out.println(result);
	}
	private static int findp(int s) {
		// TODO Auto-generated method stub
		if(p[s]==s) {
			return p[s];
		}
		p[s]=findp(p[s]);
		return p[s];
	}
	

}