[BOJ] 사이클 게임(20040)

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

문제 : BOJ_20040번 사이클 게임

문제 설명

n 개의 노드가 주어지고, m 개의 양방향 선이 주어졌을 때, 최초로 사이클이 완성되는 m 번 째를 출력하는 문제입니다.

모든 m을 순회해도 사이클이 생기지 않았다면, 0을 출력해야 합니다.

---

Solution

유니온 파인드

n이 최대 500,000이므로 O(n) 만에 답을 출력해야 합니다.

유니온 파인드를 사용해야 합니다.

이어지는 두 점을 merge 하면서 진행합니다.

merge 하기 전에 주어진 두 점이 같은 조상이라면, 같은 조상을 갖고 있는 노드끼리 이어지므로 사이클이 됩니다.

이때의 m을 출력해 줘야 합니다.

---

Description

• vector를 이용해 n과 m에 값에 맞는 배열을 동적할당했습니다.

---

#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<int> parent;
vector<int> level;
int find(int u){
    if(u==parent[u]) return u;
    return parent[u] = find(parent[u]);
}
void merge(int u, int v)
{
    u = find(u);
    v = find(v);

    if (u == v)
        return;

    if (level[u] > level[v]) swap(u, v);

    parent[u] = v;

    if (level[u] == level[v]) ++level[v];
}

int main(){
    cin >> n >> m;
    parent.resize(n+1);
    level.resize(n+1);
    for(int i=1;i <=n;i++){
        parent[i]=i;
        level[i]=1;
    }
    int swc = 0;
    for(int i=1;i<=m;i++){
        int st, ed;
        cin >> st >> ed;
        if(find(st) == find(ed)) {
            swc=i;
            break;
        }
        merge(st,ed);
    }
    cout << swc << '\n';
}