[C++] 사이클 게임 (백준 20040번)

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

 

유니온 파인드를 이용하여 간선을 하나씩 추가하면서 사이클이 처음 생기는 순간만 찾아주면 된다.

a와 b가 이미 같은 집합인데 a와 b를 연결하는 간선이 들어오면 사이클이 생긴 것이라고 판단하면 된다.

 

#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<int> parent;

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

int unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
        parent[b] = a;
        return true;
    } else {
        return false; // 사이클 발생
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    
    parent = vector<int>(n + 1);
    for (int i = 0; i < n; i++) parent[i] = i;

    for (int i = 1; i < m + 1; i++) {
        int a, b;
        cin >> a >> b;
        if (!unite(a, b)) {
            cout << i << '\n';
            return 0;
        }
    }

    cout << "0\n";
}

(AC)