[백준] 20040 - 사이클 게임

[문제링크]

20040번: 사이클 게임

 

0. disjoint set 문제

 

1. A에서 B로 선분을 그으려 할 때, 이미 A와 B가 같은 집합에 속한다면 사이클이 생성된다

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		
		init(n);
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = pint(st.nextToken());
			int y = pint(st.nextToken());
			if(!union(x,y)) {
				System.out.println(i+1);
				break;
			}
			else if(i==m-1) {
				System.out.println(0);
			}
		}
		
	}
	static int[] parents;
	
	static void init(int n) {
		parents=new int[n];
		for (int i = 0; i < n; i++) {
			parents[i]=i;
		}
	}
	
	static int find(int n) {
		if(parents[n]!=n)return parents[n]=find(parents[n]);
		return n;
	}
	
	static boolean union(int x, int y) {
		int px=find(x), py=find(y);
		if(px==py)return false;
		
		parents[px]=py;
		return true;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면