[백준] 20040번 : 사이클 게임 - JAVA [자바]

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

20040번: 사이클 게임

---

문제

 

이 문제는 유니온파인드로 풀 수 있다.

문제가 요구하는 것은 간단하다. 그래프(집합)을 형성할때, 만약 사이클이 발생한다면, 그 차례의 수를 출력하는 것이다.

 

생각을 해보자 사이클은 언제 발생 될까?

 

두개의 점을 그래프를 연결하기전에 이미 두개의 점들의 대표자가 같다면 싸이클이다. - 그림을 그려보면 쉽게 알 수 있다.

아래는 실제로 풀면서 내가 그린 그림이다.

 

이점을 이용해서 유니온파인드 기본코드에서 위의 조건문만 추가해주면 쉽게 풀 수 있는 문제이다. 

---

전체 코드

public class Main {
    static int n, m;
    static int[] arr;
    
	public static void main(String[] args) throws Exception {
    	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	StringBuilder sb = new StringBuilder();
    	StringTokenizer st;
    	
    	st = new StringTokenizer(in.readLine());
    	
    	n = Integer.parseInt(st.nextToken());
    	m = Integer.parseInt(st.nextToken());
    	
    	arr = new int[n];
    	makeSet();
    	
    	int result = 0;
    	
    	for(int c = 0; c < m; c++) {
    		st = new StringTokenizer(in.readLine());
    		
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		
    		// 연결할 때 a의 부모와 b의 부모가 이미 같다면 이것은 사이클이다. 
    		if(findSet(a) == findSet(b)) {
    			result = c + 1;
    			break;
    		}
    		
    		union(a, b);
    	}
    	
    	System.out.println(result);
    	
    }
	static void makeSet() {
		for(int i = 0; i < n; i++) {
			arr[i] = i;
		}
	}
	
	static int findSet(int x) {
		if(x == arr[x]) {
			return x;
		}
		
		return arr[x] = findSet(arr[x]);
	}
	
	static void union(int x, int y) {
		if(x != y) {
			arr[findSet(y)] = findSet(x);
		}
	}
}

 

---

결과