【今日の精進】ABC286G - Unique Walk

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

問題リンク

atcoder.jp

問題概要

グラフが与えられるよ。

指定された辺はちょうど1回、それ以外は何回でも通っていいような経路が存在するか判定してね。

解法

何回でも通っていい辺がごちゃごちゃしていると見通しが立てづらいので、いっそのことUnionFindなどでまとめてしまいましょう。

そうすると、指定された辺しか残らないような新しいグラフを作ることができます。そのため、「すべての辺を1回だけ通る経路」と読み替えることができます。

そしてこれは有名問題で、要するに一筆書き*1です。

存在判定は、次数が奇数の頂点数が0か2であるかを見るだけでよいです。

オイラー路が構成できる場合、元のグラフでも題意を満たす経路が存在することを示すことは容易です。

提出コード

class UnionFind():
    def __init__(self,size):
        self.uf=[[-1,0,1] for i in range(size)]
        
    def unite(self,fir,sec):
        one=self.root(fir)
        two=self.root(sec)
        if one!=two:
            if self.uf[one][1]>self.uf[two][1]:
                one,two=two,one
            self.uf[one][0]=two
            self.uf[two][2]+=self.uf[one][2]
            if self.uf[one][1]==self.uf[two][1]:
                self.uf[two][1]+=1
    
    def same(self,fir,sec):
        return self.root(fir)==self.root(sec)
    
    def root(self,node):
        pos=node
        change=[]
        while self.uf[pos][0]!=-1:
            change.append(pos)
            pos=self.uf[pos][0]
        for i in change:
            self.uf[i][0]=pos
        return pos
    
    def size(self,node):
        return self.uf[self.root(node)][2]

N,M=map(int,input().split())
edge=[tuple(map(int,input().split())) for i in range(M)]
K=int(input())
x=set(map(int,input().split()))
union=UnionFind(N)
for i in range(M):
    if i+1 not in x:
        union.unite(edge[i][0]-1,edge[i][1]-1)
cnt=[0]*N
for i in range(M):
    if i+1 in x:
        cnt[union.root(edge[i][0]-1)]+=1
        cnt[union.root(edge[i][1]-1)]+=1
ans=0
for i in cnt:
    ans+=i&1
if ans<=2:
    print("Yes")
else:
    print("No")

Submission #47099316 - UL Systems Programming Contest 2023(AtCoder Beginner Contest 286)

感想

オイラー路ってこういう感じで出てくるのね

*1:厳密にはオイラー路