結果
問題 | No.2403 "Eight" Bridges of Königsberg |
ユーザー |
![]() |
提出日時 | 2023-08-04 21:48:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 168 ms / 2,000 ms |
コード長 | 756 bytes |
コンパイル時間 | 160 ms |
コンパイル使用メモリ | 82,568 KB |
実行使用メモリ | 86,400 KB |
最終ジャッジ日時 | 2024-11-26 17:46:53 |
合計ジャッジ時間 | 4,309 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
from sys import stdin input=lambda :stdin.readline()[:-1] n,m=map(int,input().split()) edge=[[] for i in range(n)] IN=[0]*n OUT=[0]*n for i in range(m): a,b=map(lambda x:int(x)-1,input().split()) IN[a]+=1 OUT[b]+=1 edge[a].append(b) edge[b].append(a) G=[] seen=[0]*n for i in range(n): if seen[i]: continue todo=[i] seen[i]=1 res=0 flag=False size=0 while todo: v=todo.pop() size+=1 if IN[v]>OUT[v]: flag=True res+=IN[v]-OUT[v] for u in edge[v]: if seen[u]==0: seen[u]=1 todo.append(u) if size!=1 or IN[i]!=0: G.append([res,flag]) ans=0 cnt1=0 cnt2=0 for x,y in G: ans+=x if y: cnt1=1 else: cnt2+=1 if cnt2==0: print(ans-1) else: print(ans+cnt2-1)