[BOJ] 20040

사이클 게임

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

분류

• Gold 4

• 자료 구조
• 분리 집합

해법

알고리즘개론 수업을 듣는데
Union Find를 사용해서 그래프에서 사이클을 찾는 알고리즘이 나와서 찾아서 풀어봤습니다.

매번 연결해야 하는 점들이 같은 집합에 속해있다면 그 두 점을 연결했을 때 사이클이 생기는 것을 이용하면 됩니다.

정답 코드

/*
BOJ 20040: 사이클 게임
*/

#include <bits/stdc++.h>
using namespace std;

int n, m;
int a, b;
int parent[500005];
int depth[500005];
int ans;

void init() {
    for (int i = 0; i < 500005; i++) {
        parent[i] = i;
    }
}

int find(int x) {
    if (x == parent[x]) {
        return x;
    }
    return parent[x] = find(parent[x]);
}

void merge(int x, int y) {
    x = find(x), y = find(y);
    // x가 더 키가 크면 바꿔준다. (y가 더 크게)
    if (depth[x] > depth[y]) {
        swap(x, y);
    }
    parent[x] = y; // x를 y밑에 붙여준다.
    if (depth[x] == depth[y])
        depth[y]++;
}

bool is_cycle(int x, int y) {
    return find(x) == find(y);
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    init();
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        if (is_cycle(a, b)) {
            ans = i + 1;
            break;
        }
        merge(a, b);
    }
    cout << ans;
    return 0;
}