사이클 게임

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

"""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()

• Dependency: teflib.disjointset.DisjointSet