문제링크 : https://www.acmicpc.net/problem/20040
접근 과정 :
- 분리 집합으로 접근하면 간단하다.
- 연결 정보에 따라서 집합으로 합쳐주고. 만약 집합의 번호가 같으면 사이클이 형성된다!!
- 사이클이 형성될 때, i를 리턴한다.
+++
비슷한 문제 : https://rays-space.tistory.com/74
20040을 풀고 4803을 풀면 사이클 문제는 익숙해지지 않을까싶다.
소스 코드 및 결과 :
package BOJ;
/*
사이클 게임
*/
import java.io.*;
import java.util.*;
public class BOJ20040 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
setRoot(n);
for (int i = 1; i <= m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
a = findRoot(a);
b = findRoot(b);
if (a == b) {
System.out.println(i);
return;
}
root[b] = a;
}
System.out.println(0);
}
static int[] root;
static void setRoot(int n) {
root = new int[n];
for (int i = 0; i < n; i++) {
root[i] = i;
}
}
static int findRoot(int x) {
if (root[x] == x) {
return x;
}
return root[x] = findRoot(root[x]);
}
}
P.S
개인적으로 입력의 중간에 결과가 나왔다고 리턴하는 것을 좋아하지 않는다..
그런데 해당 문제에서는 그렇게 해야 속도가 좀 빠르게 나오더라..
'Algorithm' 카테고리의 다른 글
[백준 Platinum 5] 2618 경찰차 - Java (0) | 2022.01.04 |
---|---|
[백준 Gold 2] 17472 다리 만들기 2 - Java (0) | 2022.01.04 |
[백준 Gold 4] 4803 트리 - Java (0) | 2022.01.03 |
[백준 Silver 3] 9372 상근이의 여행 - Java (0) | 2022.01.03 |
[백준 Gold 3] 11812 K진 트리 - Java (0) | 2022.01.03 |