백준[20040] 사이클게임

풀이 방법

유니온 파인드라는 자료구조를 이용하여 풀이하였다.

입력받은 두개의 루트 노드가 같으면 사이클이 형성되었다고 판단하고, 다르다면 두개의 트리를 합친다.

 

코드

 

#include <cstdio>
#include <algorithm>

using namespace std;

int par[500005], level[500005];

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

void merge(int x, int y) {
    int a = find(x), b = find(y);
    if (a == b) return;
    if (level[a] > level[b]) swap(a, b);
    if (level[a] == level[b]) level[b]++;
    par[a] = b;
}

int main() {
    int N, M; scanf("%d %d", &N, &M);
    for (int i = 0; i <= N; i++) {
        par[i] = i;
        level[i] = 1;
    }
    for (int i = 1; i <= M; i++) {
        int a, b; scanf("%d %d", &a, &b);
        int x = find(a), y = find(b);
        if (x != y) merge(x, y);
        else { printf("%d", i); return 0; }
    }
    printf("0");
}

문제 링크: https://www.acmicpc.net/problem/20040