[백준] 20040 사이클 게임

문제 출처: www.acmicpc.net/problem/20040

20040번: 사이클 게임

: 주어진 경로를 이어가면서 사이클이 발생한다면 몇번째에서 발생하는지 발생하지 않으면 0을 출력할 수 있도록 한다.

: 유니온 파인드 알고리즘을 통해 풀 수 있고, union 메소드가 boolean 값을 반환하기 때문에 사이클이 발생하면 그 즉시 중단할 수 있도록 한다.

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int[] p;
	static int N;
	private static void make() {
		for(int i = 0; i < N; i++)
			p[i] = i;
	}
	private static int find(int idx) {
		if(p[idx] == idx) return idx;
		return p[idx] = find(p[idx]);
	}
	private static boolean union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		if(aRoot == bRoot) return false;
		p[bRoot] = aRoot;
		return true;
	}
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		p = new int[N];
		make();
		int ans = 0;
		for(int i = 1; i < K+1; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if(!union(a, b)) {
				ans = i;
				break;
			}
		}
		System.out.println(ans);
		
	}
}