[백준 20040] 사이클 게임

 

 문제의 이름에서도 예상할 수 있듯이 Disjoint Set(Union-Find) 문제다. 

 디테일한 요구 사항은 따로 없어서, 일반적으로 구현하는 Union Find를 그대로 이용하면 된다. 선택된 두 점이 이미 같은 집합 내에 있는 경우, 잇게 되면 사이클이 발생하므로 처음으로 선택된 두 점이 이미 같은 집합인 경우를 찾아내면 된다. 

 나는 Union 로직에서 이미 두 점의 루트 노드를 Find 하게 되므로 그때 비교한 결과가 같다면 false를 리턴하도록 해 판별했다.

 다만 n이 최대 500,000이고 m이 최대 1,000,000이라, 경로 압축 정도는 적용해주어야 한다. 안 그러면 Find 연산이 최악의 경우 O(n)에 근사하기 때문에 제 시간 내에 풀리지 않을 것이다.

 

#include <iostream> 
#include <vector>

using namespace std;

vector<int> root;

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

bool makeUnion(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);

    if(rootX==rootY) return false;

    if(rootX<rootY) {
        root[rootY] = rootX;
    } else {
        root[rootX] = rootY;
    }
    return true;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    root = vector<int>(n);
    for(int i=0; i<n; i++) {
        root[i] = i;
    }

    int cycleOccur = 0;
    int p1, p2;
    for(int i=0; i<m; i++) {
        cin >> p1 >> p2;
        if(cycleOccur!=0) continue;
        if(!makeUnion(p1, p2)) {
            cycleOccur = i+1;
        }
    }

    cout << cycleOccur;
}