[BaekJoon] 백준 20040번 : 사이클 게임

20040번 : 사이클 게임

선 플레이어가 홀수 번.. 후 플레이어가 짝수 번.. 선분 긋기.. 말이 길다

결국 문제를 쭉 읽어보면 엣지 정보를 통해 그래프를 이어가다가 몇 번째 엣지에서 사이클이 발생하는지 찾는 문제이다.

그래프를 만들어가면서 사이클 여부를 확인하려면 union-find 방법이 가장 좋다.

union-find 를 통해 부모를 정해가다가 두 노드의 부모가 같은 경우 사이클이 발생 한 것이다.

---

import sys


def find_parent(node, parent):
    if parent[node] != node:
        parent[node] = find_parent(parent[node], parent)

    return parent[node]


def union_parent(a, b, parent):
    a = find_parent(a, parent)
    b = find_parent(b, parent)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b


def solution():
    answer = 0

    parent = [i for i in range(N)]
    for idx, edge in enumerate(edges):
        a, b = edge
        if find_parent(a, parent) != find_parent(b, parent):
            union_parent(a, b, parent)
        else:
            answer = idx + 1
            break

    return answer


if __name__ == "__main__":
    N, M = map(int, input().split())
    edges = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(M)]

    print(solution())