백준 20040번
https://www.acmicpc.net/problem/20040
그래프에서 사이클을 찾으면 되는 문제이다.
유니온 파인드를 통해서 문제 해결이 가능하다.
사이클은 두 노드의 부모가 같으면 사이클이 된다.
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if (find(a) == find(b)) {
sb.append(i + 1);
return sb.toString();
}
입력 받은 두 노드가 같은 부모가 가지는지 확인하고 아닐 경우 union()
메소드를 실행하면 된다.
import java.io.*;
import java.util.StringTokenizer;
public class Main {
// input
private static BufferedReader br;
// variables
private static int N, M;
private static int[] parents, ranks;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
input();
bw.write(solve());
bw.close();
} // End of main()
private static String solve() throws IOException {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if (find(a) == find(b)) {
sb.append(i + 1);
return sb.toString();
}
union(a, b);
}
sb.append(0);
return sb.toString();
} // End of solve()
private static void union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA == rootB) return;
if (ranks[rootA] < ranks[rootB]) {
// A가 더 부모임
parents[rootA] = rootB; // rootA의 부모는 rootB로 변경
} else {
// rootA의 높이가 더 높거나 같을 경우
parents[rootB] = rootA; // rootB의 부모가 rootA가 된다.
// 이미 A의 높이가 더 높을경우에는 A가 부모가 되고 높이는 증가시키지 않는다.
if (ranks[rootA] == ranks[rootB]) {
ranks[rootA]++; // A가 B의 부모가 되어서 rank가 증가한다.
}
}
} // End of union()
private static int find(int node) {
if (parents[node] == node) return node;
return find(parents[node]);
} // End of find()
private static void input() throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
parents = new int[N];
ranks = new int[N];
for (int i = 1; i < N; i++) {
parents[i] = i;
}
} // End of input()
} // End of Main class