[BOJ 20040 | C++] 사이클 게임 :: Union-Find

• 문제 링크 : https://www.acmicpc.net/problem/20040
• 문제 태그 : 자료 구조, 분리 집합
• 관련 문제 : 2025.02.15 - [BOJ] - [BOJ 1717 | C++] 집합의 표현 :: Union-Find

[BOJ 1717 | C++] 집합의 표현 :: Union-Find

 

풀이

경로 압축과 union-by-size를 이용했습니다.

 

사이클은 입력받은 두 정점이 이미 같은 집합에 속해 있는 상태에서, 두 정점을 연결하는 간선을 추가할 경우 발생한다고 판정했습니다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> p(n, -1);
    
    auto find = [&](int x) {
        int root = x;
        while(p[root] >= 0) root = p[root];
        while(x != root) {
            int nxt = p[x];
            p[x] = root;
            x = nxt;
        }
        return root;
    };
    
    auto merge = [&](int u, int v) -> bool {
        u = find(u);
        v = find(v);
        
        if (u == v) return 0;
        if (-p[u] < -p[v]) swap(u, v);
        
        // u의 size가 더 크다
        p[u] += p[v];
        p[v] = u;
        return 1;
    };
    
    for (int i = 1;i <= m;i++) {
        int u, v;
        cin >> u >> v;
        
        if (!merge(u, v)) {
            cout << i;
            return 0;
        }
    }
    cout << 0;
}