사용자 도구

사이트 도구


ps:problems:boj:20040

사이클 게임

ps
링크acmicpc.net/…
출처BOJ
문제 번호20040
문제명사이클 게임
레벨골드 4
분류

Disjoint set

시간복잡도O(m*α(n))
인풋사이즈n<=500,000, m<=1,000,000
사용한 언어Python
제출기록38224KB / 1016ms
최고기록736ms
해결날짜2021/10/15
태그

29단계

풀이

  • 선분을 하나씩 그려나갈때마다 연결된 상태들을 업데이트해주고, 이미 연결되어있는 두 점에 대해서 선분을 추가하게 되는 경우 사이클이 생긴걸로 처리하면 된다.
  • 점들의 연결 상태를 확인하고 업데이트하는 것은 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()

토론

댓글을 입력하세요:
A P A S​ P
 
ps/problems/boj/20040.txt · 마지막으로 수정됨: 2021/10/17 15:12 저자 teferi