結果

問題 No.583 鉄道同好会
コンテスト
ユーザー vwxyz
提出日時 2021-12-30 07:17:55
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 5,045 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 13,312 KB
実行使用メモリ 40,320 KB
最終ジャッジ日時 2024-10-05 12:51:39
合計ジャッジ時間 3,293 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 4 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
import sys
readline=sys.stdin.readline
read=sys.stdin.read

class Graph:
    def __init__(self,V,edges=False,graph=False,directed=False,weighted=False,inf=float("inf")):
        self.V=V
        self.directed=directed
        self.weighted=weighted
        self.inf=inf
        if not graph:
            self.edges=edges
            self.graph=[[] for i in range(self.V)]
            if weighted:
                for i,j,d in self.edges:
                    self.graph[i].append((j,d))
                    if not self.directed:
                        self.graph[j].append((i,d))
            else:
                for i,j in self.edges:
                    self.graph[i].append(j)
                    if not self.directed:
                        self.graph[j].append(i)
        else:
            self.graph=graph
            self.edges=[]
            for i in range(self.V):
                if self.weighted:
                    for j,d in self.graph[i]:
                        if self.directed or not self.directed and i<=j:
                            self.edges.append((i,j,d))
                else:
                    for j in self.graph[i]:
                        if self.directed or not self.directed and i<=j:
                            self.edges.append((i,j))

    def Euler_Path(self,s=None,t=None):
        if self.directed:
            indegree=[0]*self.V
            outdegree=[0]*self.V
            graph=[[] for x in range(self.V)]
            for tpl in self.edges:
                if self.weighted:
                    u,v,d=tpl
                else:
                    u,v=tpl
                indegree[v]+=1
                outdegree[u]+=1
                graph[v].append(u)
            for x in range(self.V):
                if indegree[x]+1==outdegree[x]:
                    if s==None:
                        s=x
                    elif s!=x:
                        return False
                elif indegree[x]==outdegree[x]+1:
                    if t==None:
                        t=x
                    elif t!=x:
                        return False
                elif indegree[x]!=outdegree[x]:
                    return False
            if (s,t)==(None,None):
                for x in range(self.V):
                    if graph[x]:
                        s=x
                        t=x
                        break
            elif s==None:
                s=t
            elif t==None:
                t=s
            elif s==t:
                for x in range(self.V):
                    if indegree[x]!=outdegree[x]:
                        return False
            queue=[t]
            euler_path=[]
            while queue:
                while graph[queue[-1]]:
                    queue.append(graph[queue[-1]].pop())
                x=queue.pop()
                euler_path.append(x)
            for x in range(self.V):
                if graph[x]:
                    return False
        else:
            degree=[0]*self.V
            graph=[[] for x in range(self.V)]
            use_count=[defaultdict(int) for x in range(self.V)]
            for tpl in self.edges:
                if self.weighted:
                    u,v,d=tpl
                else:
                    u,v=tpl
                degree[v]+=1
                degree[u]+=1
                graph[u].append(v)
                graph[v].append(u)
            for x in range(self.V):
                if degree[x]%2:
                    if s==None and t!=x:
                        s=x
                    elif t==None and s!=x:
                        t=x
                    elif not x in (s,t):
                        return False
            if s==None and t==None:
                for x in range(self.V):
                    if graph[x]:
                        s=x
                        t=x
                        break
                else:
                    s,t=0,0
            elif s==None:
                s=t
            elif t==None:
                t=s
            elif s!=t:
                if degree[s]%2==0 or degree[t]%2==0:
                    return False
            queue=[t]
            euler_path=[]
            while queue:
                while graph[queue[-1]]:
                    if use_count[queue[-1]][graph[queue[-1]][-1]]:
                        use_count[queue[-1]][graph[queue[-1]][-1]]-=1
                        graph[queue[-1]].pop()
                    else: 
                        queue.append(graph[queue[-1]].pop())
                        use_count[queue[-1]][queue[-2]]+=1
                x=queue.pop()
                euler_path.append(x)
            for x in range(self.V):
                if graph[x]:
                    return False
        if euler_path[0]!=s:
            return False
        return euler_path

N,M=map(int,readline().split())
edges=[]
for _ in range(M):
    a,b=map(int,readline().split())
    edges.append((a,b))
G=Graph(N,edges=edges)
path=G.Euler_Path()
if path:
    ans="YES"
else:
    ans="NG"
print(ans)
0