테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 사이클 게임 ======

===== 풀이 =====
  * 선분을 하나씩 그려나갈때마다 연결된 상태들을 업데이트해주고, 이미 연결되어있는 두 점에 대해서 선분을 추가하게 되는 경우 사이클이 생긴걸로 처리하면 된다.
  * 점들의 연결 상태를 확인하고 업데이트하는 것은 [[ps:Disjoint Set]]을 사용하면 O(α(n))에 가능하다. 최대 m개의 선분에 대해서 처리해야 하므로 총 시간복잡도는 O(m*α(n))

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 20040. 사이클 게임".

- Problem link: https://www.acmicpc.net/problem/20040
- Solution link: http://www.teferi.net/ps/problems/boj/20040

Tags: [DisjointSet]
"""

import sys
from teflib import disjointset


def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    dsu = disjointset.DisjointSet(n)
    for i in range(m):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        try:
            dsu.union(a, b, should_raise=True)
        except ValueError:
            print(i + 1)
            break
    else:
        print('0')


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:disjointset#DisjointSet|teflib.disjointset.DisjointSet]]

{{tag>BOJ ps:problems:boj:골드_4}}