[백준 / C++] 20040번: 사이클 게임

백준 20040번: 사이클 게임
알고리즘 분류: 자료 구조, 분리 집합

백준 문제 바로가기

🤨 Hmm...

입력으로 두 점이 차례로 주어질 때 몇 차례에 사이클이 생성되는지 판단하는 문제이다.

분리 집합을 사용하면 된다.

union 연산을 하기 전에 두 점의 parent를 비교하여 같으면 사이클이 생성될 예정이므로 그 즉시 순번을 반환하면 된다.

다르다면 union 연산을 하면 된다.

💻 소스 코드

#include <iostream>
#include <algorithm>
#define int long long
#define fastIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;

class BJ {
    int n, m;
    int *parent;
public:
    BJ();
    int findParent(int x);
    void unionParent(int x, int y);
};

BJ::BJ() {
    cin >> n >> m;

    parent = new int[n];
    for (int i = 0; i < n; i++)
        parent[i] = i;

    int a, b;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        int pa = findParent(a);
        int pb = findParent(b);
        if (i % 2 == 1) {
            if (pa == pb) {
                cout << i;
                return;
            }
        }
        else {
            if (pa == pb) {
                cout << i;
                return;
            }
        }
        unionParent(a, b);
    }
    cout << 0;
}
int BJ::findParent(int x) {
    if (parent[x] == x)
        return x;
    parent[x] = findParent(parent[x]);
    return parent[x];
}
void BJ::unionParent(int x, int y) {
    int px = findParent(x);
    int py = findParent(y);
    if (px <= py)
        parent[py] = px;
    else
        parent[px] = py;
}

signed main(){
    fastIO;

    BJ a;
}