結果

問題 No.583 鉄道同好会
ユーザー vwxyzvwxyz
提出日時 2021-12-30 07:18:16
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 547 ms / 2,000 ms
コード長 5,045 bytes
コンパイル時間 124 ms
コンパイル使用メモリ 13,312 KB
実行使用メモリ 40,320 KB
最終ジャッジ日時 2024-04-15 14:50:29
合計ジャッジ時間 2,941 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
11,136 KB
testcase_01 AC 32 ms
11,264 KB
testcase_02 AC 32 ms
11,264 KB
testcase_03 AC 32 ms
11,392 KB
testcase_04 AC 33 ms
11,136 KB
testcase_05 AC 32 ms
11,392 KB
testcase_06 AC 33 ms
11,136 KB
testcase_07 AC 33 ms
11,264 KB
testcase_08 AC 32 ms
11,264 KB
testcase_09 AC 32 ms
11,264 KB
testcase_10 AC 34 ms
11,392 KB
testcase_11 AC 92 ms
15,744 KB
testcase_12 AC 113 ms
17,408 KB
testcase_13 AC 117 ms
17,408 KB
testcase_14 AC 114 ms
17,408 KB
testcase_15 AC 140 ms
19,456 KB
testcase_16 AC 240 ms
26,752 KB
testcase_17 AC 281 ms
29,696 KB
testcase_18 AC 547 ms
40,320 KB
権限があれば一括ダウンロードができます

ソースコード

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="NO"
print(ans)
0