악곱 == 악성곱슬

유니온-파인드

---

이 문제는 간선들의 정보가 주어지고 이를 이었을 때 사이클이 언제 발생하는지 출력하는 문제이다. 이런 유형의 경우 union-find를 이용해서 root노드가 같을 경우를 사이클로 판별하면 되는 문제이다.

따라서 간단하게 union, find 함수를 구현하고 find == find 라면 stop하고 출력하면 되는 문제이다.

구현

---

import sys

def find(x, parent):
    if x != parent[x]:
        parent[x] = find(parent[x], parent)
    return parent[x]

def union(a, b, parent):
    a = find(a, parent)
    b = find(b, parent)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
    return parent

def solution(n):
    parent = [i for i in range(n)]
    for i in range(len(edges)):
        a, b = edges[i][0], edges[i][1]
        if find(a, parent) == find(b, parent):
            return i + 1
        parent = union(a, b, parent)
    return 0

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().rstrip().split())
    edges = []
    for _ in range(M):
        A, B = map(int, sys.stdin.readline().rstrip().split())
        edges.append([A, B])
    print(solution(N))