Link | 백준 20040번 문제 : 사이클 게임
부분 집합을 통해 문제를 해결할 수 있다.
이는 Union & find 알고리즘을 통해 구현할 수 있다.
M개의 선분을 차례대로 탐색한다.
선분을 탐색할 때 우선 find 함수를 통해 두 선분을 이었을 때 cycle이 생기는지 판단한다.
Cycle이 생기면 해당 순서에서 cycle이 발생한 것이다.
Cycle이 생기지 않는다면 union 함수를 통해 선분을 부분 집합에 추가해준다.
private int[] roots;
public void solve() throws IOException {
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(tokenizer.nextToken());
int M = Integer.parseInt(tokenizer.nextToken());
roots = IntStream.range(0, N).toArray();
int m = 1;
for (; m <= M; m++) {
tokenizer = new StringTokenizer(reader.readLine());
int nodeA = Integer.parseInt(tokenizer.nextToken());
int nodeB = Integer.parseInt(tokenizer.nextToken());
int rootA = find(nodeA);
int rootB = find(nodeB);
if (rootA == rootB) break;
union(rootA, rootB);
}
result.append(m <= M ? m : 0);
}
private int find(int node) {
if (node == roots[node]) return node;
else return find(roots[node]);
}
private void union(int rootA, int rootB) {
if (rootA < rootB) roots[rootB] = rootA;
else roots[rootA] = rootB;
}