백준 22040 - 사이클 게임 [Python]

https://www.acmicpc.net/problem/20040

20040번: 사이클 게임

Union-Find 기초문제이다.

 

두 점을 선분으로 잇기 전에, 이 두 점이 다른 경로로 이미 연결되어있다면 사이클을 형성할 것이다.

다른 경로로 이미 연결되어있는지에 대한 여부는 Union-FInd를 이용하면 된다.

 

0. 입력이 들어온다.

1. 두 점의 그룹이 같은지 확인한다.

2-1. 같다면 답을 출력하고 바로 종료한다.

2-2. 다르다면 두 점의 그룹을 하나로 합쳐준다.

3. 주어진 모든 간선이 멀쩡히 잘 이어졌다면, 0을 출력한다

 

Pypy3에서는 메모리 초과가 뜬다. 재귀 제한때문에 그런듯

 

템플릿 코드

import sys, math
import heapq
 
from collections import deque
input = sys.stdin.readline
 
hqp = heapq.heappop
hqs = heapq.heappush
 
#input
def ip(): return int(input())
def sp(): return str(input().rstrip())
 
def mip(): return map(int, input().split())
def msp(): return map(str, input().split().rstrip())
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split().rstrip()))
 
#gcd, lcm
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
 
def lcm(x, y):
    return x * y // gcd(x, y)
 
#prime
def isPrime(x):
    if x<=1: return False
    for i in range(2, int(x**0.5)+1):
        if x%i==0:
            return False
    return True
 
# Union Find
# p = {i:i for i in range(1, n+1)}
def find(x):
    if x == p[x]:
        return x
    q = find(p[x])
    p[x] = q
    return q
 
def union(x, y):
    x = find(x)
    y = find(y)
 
    if x != y:
        p[y] = x
 
def getPow(a, x):
    ret = 1
    while x:
        if x&1:
            ret = (ret * a) % MOD
        a = (a * a) % MOD
        x>>=1
    return ret
 
def getInv(x):
    return getPow(x, MOD-2)

 

union()과 find()는 위의 템플릿 코드에 들어있다.

sys.setrecursionlimit(10**6)
 
n, m = mip()
 
p = [i for i in range(n)]
 
for i in range(1, m + 1):
    a, b = mip()
    if find(a) == find(b):
        print(i)
        exit()
    union(a, b)
print(0)