Submission #7917160

---

Source Code Expand

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

"""
・マッチング、と見せかけて、2辺を組にして取っていく。
・これは、連結成分上の辺の数が偶数ならできる。例えば全域木をとって根から遠い葉のまわりから処理していく。
・「1辺除いたとき、辺の数が奇数であるような連結成分ありますか？」に答える
・辺が奇数個の連結成分が唯一のときだけが問題。そのときは橋の検出アルゴリズム
"""

N = int(readline())
m = map(int,read().split())
X = []; Y = []
for x,y in zip(m,m):
    X.append(x-1)
    Y.append(y+N+N)

# とりあえず連結成分に分ける
_,comp = connected_components(csr_matrix(([1]*(N+N+1),(X,Y)),(4*N+2,4*N+2)))

comp_size = [0] * (4*N+2) # 「成分内の辺の個数」
for x,y in zip(X,Y):
    comp_size[comp[x]] += 1

comp_size

odd_comp = [i for i,x in enumerate(comp_size) if x&1]

if len(odd_comp) > 1:
    print('\n'.join('NG' for _ in range(N+N+1)))
    exit()

raise Exception

Submission Info

Judge Result