[백준 20040번] 사이클 게임

문제 링크

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

 

문제 요약

\(N\)개의 점이 있다. 이때 서로 다른 두 개의 점을 연결하는 선분들이 차례대로 주어졌을 때, 사이클이 생기는 순간을 찾는 문제이다.

 

문제 풀이

각 점을 노드로, 선분을 간선으로 하는 무향 그래프로 모델링을 한다. 새로운 간선을 추가할 때마다 두 노드가 같은 집합에 속해 있는지 확인한다. 만약 같은 집합에 속해 있다면, 해당 간선을 추가하면 사이클이 형성되는 것이다. 반대로, 같은 집합에 속해있지 않으면 두 집합을 합쳐서 하나의 집합으로 만든다. 유니온 파인드(Union Find) 자료구조를 이용해 집합을 효율적으로 관리할 수 있으며, 제한시간 내에 문제를 해결할 수 있다.

 

소스 코드

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

// Union Find 자료구조
struct UnionFind {
    vector<int> parent;
    vector<int> rank;
    
    UnionFind(int n): rank(n, 1), parent(n) {
        for (int i = 0 ; i < n ; ++i) {
            parent[i] = i;
        }
    }
    
    int find(int u) {
        if (u == parent[u]) {
            return u;
        }
        
        return parent[u] = find(parent[u]);
    }
    
    bool merge(int u, int v) {
        u = find(u);
        v = find(v);
        
        if (u == v) {
            return false;
        }
        
        if (rank[u] > rank[v]) {
            swap(u, v);
        }
        
        parent[u] = v;
        
        if (rank[u] == rank[v]) {
            ++rank[v];
        }
        
        return true;
    }
};

int main() {
    int n, m;
    
    scanf("%d%d", &n, &m);
    
    UnionFind uf(n + 1);
    
    for (int i = 1 ; i <= m ; ++i) {
        int u, v;
        
        scanf("%d%d", &u, &v);
        
        if (!uf.merge(u, v)) {
            printf("%d\n", i);
            
            return 0;
        }
    }
    
    puts("0");
}