[Algorithm] BaekJoon : 20040. 自転車ゲームbypython

[問題のショートカット]https://www.acmicpc.net/problem/20040

📌問題の説明

自転車ゲームは2人のプレイヤーが順次行うゲームで、先にプレイヤーが単数回、後にプレイヤーが偶数回行う.ゲーム開始時、0からnまで、平面上にn個の点に一意の番号が付けられ、いずれの点も直線上に置かれない.プレイヤーは毎回2つの点を選択してこの2つの点を結ぶ線分を描きます.以前描いた線分はもう描くことはできませんが、すでに描いた他の線分と交差することができます.ゲームをして初めて自転車を完成した瞬間、ゲームは終わりました.ループCはプレイヤーが描いた線分の部分集合であり、以下の条件を満たす.
Cに属する任意の線分の1つの端点から出発して、各線分は1回通過して、それから起点に戻ることができます.
問題は、複数の線分を描くことでループが完了したかどうかを判断するのが難しく、ループが完了してもゲームを続けることができるということです.この問題を解決するために,所定のゲームの進行状況が与えられた場合,何回目の完了サイクルを判断するか,ゲームが進行中であるかを判断するプログラムを作成する.
入力点の個数nとゲームがmに進む順番であれば、サイクルが完了するか否かを判断し、完了すれば、何回目に1回目の完了サイクルを出力するプログラムを作成する.
入力
入力は標準入力です.入力された最初の行は、整数3≦n≦500000、および整数3≦m≦1000000を与え、実行回数を表す.ゲームで使用されるn個の点には0からnから1までの一意の番号が付けられており、いずれの3個の点も一直線上に置かれない.次のm個の入力ラインでは、各入力ラインにi回目に選択した2点の番号(1≦i≦m)が付与される.
しゅつりょく
出力は標準出力を採用する.所定のエンクロージャを入力する場合、m回までのゲームの場合、ゲームが終了している場合は、ループが最初に作成された次数を正の整数に出力し、m回の処理が終了していない場合は0を出力する.

💡 問題を解く

実装集合のコードを用いて周期を識別することができる.
周期は、接続する2つのノードの親(親)ノード情報で識別できます.
※問題解決プロセス
(1)所与の幹線情報でノードを接続する.
(2)接続する2つのノードの親ノードが異なる場合は,2つのノードを接続する.→このとき、番号(値)の小さいノードを親ノードに設定します.
(3)プロセスで接続しようとしている2つのノードの親ノードが同じ場合は、「ループ」が生成され、対応する順序が出力されます.
→n 1,n 2両ノードの場合、親ノードは同一であり、n 1,n 2ノードが同一の特定ノードに接続されていることを示す.この場合、n 1,n 2を接続すると、ループが形成される.
ex)親ノード=0とn 1,n 2=1,2の場合
幹線の情報に[(0,1),(0,2),(1,2)]]が付与されると、親=[0,0]となる.
「相互集合」の符号化のみを実現すれば,この問題は容易に解決できる.
コードは次のとおりです.

import sys

def find_parent(x): # 부모 노드 찾기
    if x != parents[x]:
        return find_parent(parents[x])
    return x

def union_parent(n1, n2): # 두 노드(n1, n2) 연결하기
    n1 = find_parent(n1)
    n2 = find_parent(n2)
    if n1 < n2: # 노드의 번호(값)가 작은 노드에 연결하기
        parents[n2] = n1
    else:
        parents[n1] = n2

n, m = map(int, input().split())
parents = [i for i in range(n)] # 부모 노드를 알려주는 배열(초기값 = 자기자신의 번호)
edges = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]

for idx, info in enumerate(edges): # 차례의 번호를 알기위해 enumerate 사용
    if find_parent(info[0]) != find_parent(info[1]): # 부모 노드가 서로 다르면 연결
        union_parent(info[0], info[1])
    else: # 사이클 발생
        print(idx+1)
        break
else:
    print(0)