문제 : boj20040
N개의 정점이 있는 그래프에 대해 M개의 간선을 순서대로 연결하면서 사이클이 언제 생기는지 파악하면 된다. 즉, 간선을 연결하는 중에 사이클 판정만 할 수 있다면 풀 수 있다.
내 경우엔 union-find를 사용해 disjoint set(분리 집합)에 대해 판단했다. 새로운 간선을 연결했을 때, 연결한 두 정점이 동일한 그룹이라면 사이클이 생긴 경우이므로, 현재까지 연결한 간선의 개수를 카운팅한걸 답으로 출력하면 된다. 모든 간선을 연결해도 사이클이 생기지 않았다면 0을 출력하면 된다.
코드 : github
import java.io.DataInputStream;
import java.io.IOException;
import java.util.Arrays;
public class Main extends FastInput {
private int[] parents;
private int find(int a) {
if (parents[a] < 0) return a;
return a = find(parents[a]);
}
private boolean union(int a, int b) {
a = find(a);
b = find(b);
if (a==b) return true;
int h = parents[a]<parents[b]?a:b;
int l = parents[a]<parents[b]?b:a;
parents[h] += parents[l];
parents[l] = h;
return false;
}
private void solution() throws Exception {
int n = nextInt();
int m = nextInt();
parents = new int[n];
Arrays.fill(parents, -1);
for (int i = 1; i <= m; i++) {
if (union(nextInt(), nextInt())) {
System.out.println(i);
return;
}
}
System.out.println(0);
}
public static void main(String[] args) throws Exception {
initFI();
new Main().solution();
}
}
class FastInput {
private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
private static DataInputStream inputStream;
private static byte[] buffer;
private static int curIdx, maxIdx;
protected static void initFI() {
inputStream = new DataInputStream(System.in);
buffer = new byte[DEFAULT_BUFFER_SIZE];
curIdx = maxIdx = 0;
}
protected static int nextInt() throws IOException {
int ret = 0;
byte c = read();
while (c <= ' ') c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
return ret;
}
private static byte read() throws IOException {
if (curIdx == maxIdx) {
maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
if (maxIdx == -1) buffer[0] = -1;
}
return buffer[curIdx++];
}
}
'PS > BOJ' 카테고리의 다른 글
백준 2580 자바 - 스도쿠 (BOJ 2580 JAVA) (0) | 2022.01.26 |
---|---|
백준 14467 자바 - 소가 길을 건너간 이유 1 (BOJ 14467 JAVA) (0) | 2022.01.25 |
백준 1806 자바 - 부분합 (BOJ 1806 JAVA) (0) | 2022.01.23 |
백준 1450 자바 - 냅색문제 (BOJ 1450 JAVA) (2) | 2022.01.22 |
백준 2252 자바 - 줄 세우기 (BOJ 2252 JAVA) (0) | 2022.01.21 |
댓글