백준 20040 : 사이클 게임

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

20040번: 사이클 게임

[ 문제풀이 ]

두 노드가 같은 그래프에 속하는지를 판별해주면 되기 때문에 합집합 찾기(Union Find) 알고리즘을 사용해주면 쉽게 해결할 수 있는 문제이다.

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

public class Main {

	static int n, m, ans;
	static int[] parent;
	
	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))){
			StringTokenizer st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			parent = new int[n];
			for (int i = 0; i < n; ++i) parent[i] = i;
			for (int i = 1; i <= m; ++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;
				}
			}
			bw.write(ans + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public static int getParent(int v) {
		return v == parent[v] ? v : (parent[v] = getParent(parent[v]));
	}
	
	public static boolean union(int a, int b) {
		a = getParent(a);
		b = getParent(b);
		if (a == b) return false;
		parent[b] = a;
		return true;
	}
}