【今日の精進】AGC032C - Three Circuits

毎日格上の問題を倒すやつの55日目です。

問題リンク

atcoder.jp

問題概要

グラフが与えられるよ。

すべての辺を1回ずつ使って三つのサーキットを作れるか判定してね。

解法

明らかにオイラーグラフであることが必要条件です。これはすべての頂点の次数が偶数か判定すれば良いです。

また、次数が6以上の頂点があれば確実に作れます。

そのほか、次数が4以上の頂点が3つ以上あれば確実に作れることもわかります。

次数が4以上のものが存在しなければただのサイクルなので、作れないこともわかります。 次数4が1つだけでも無理です。

残ったのは次数4がちょうど2つのときです。これには作れるパターンと作れないパターンが明確に分かれています。

「一方のみを含むサイクルが存在するならば可能」です。

これはDFSするだけで容易に判定できます。

提出コード

def Yes():
    print("Yes")
    exit()

def No():
    print("No")
    exit()

N,M=map(int,input().split())
gr=[set() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    gr[a-1].add(b-1)
    gr[b-1].add(a-1)
for i in range(N):
    if len(gr[i])%2:
        No()
four=[]
for i in range(N):
    if len(gr[i])>=6:
        Yes()
    if len(gr[i])==4:
        four.append(i)
if len(four)<=1:
    No()
if len(four)>=3:
    Yes()
for i in gr[four[0]]:
    pos=i
    bef=four[0]
    while True:
        if pos==four[0]:
            Yes()
        if pos==four[1]:
            break
        for i in gr[pos]:
            if i!=bef:
                bef=pos
                pos=i
                break
No()

Submission #47564766 - AtCoder Grand Contest 032

感想

コーナーケースが詰め切れてるかめっちゃ不安になるなぁ