結果
問題 | No.2464 To DAG |
ユーザー | hirayuu_yc |
提出日時 | 2023-08-26 09:30:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,211 ms / 2,000 ms |
コード長 | 956 bytes |
コンパイル時間 | 1,894 ms |
コンパイル使用メモリ | 86,708 KB |
実行使用メモリ | 247,268 KB |
最終ジャッジ日時 | 2023-08-28 19:28:16 |
合計ジャッジ時間 | 40,856 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 92 ms
71,648 KB |
testcase_01 | AC | 92 ms
71,508 KB |
testcase_02 | AC | 1,168 ms
247,268 KB |
testcase_03 | AC | 1,185 ms
165,012 KB |
testcase_04 | AC | 1,194 ms
158,044 KB |
testcase_05 | AC | 1,185 ms
154,816 KB |
testcase_06 | AC | 1,198 ms
153,964 KB |
testcase_07 | AC | 846 ms
133,732 KB |
testcase_08 | AC | 1,008 ms
145,132 KB |
testcase_09 | AC | 938 ms
138,748 KB |
testcase_10 | AC | 952 ms
135,812 KB |
testcase_11 | AC | 715 ms
122,156 KB |
testcase_12 | AC | 611 ms
110,428 KB |
testcase_13 | AC | 731 ms
121,584 KB |
testcase_14 | AC | 814 ms
130,756 KB |
testcase_15 | AC | 1,031 ms
168,000 KB |
testcase_16 | AC | 646 ms
124,912 KB |
testcase_17 | AC | 213 ms
84,016 KB |
testcase_18 | AC | 433 ms
106,656 KB |
testcase_19 | AC | 91 ms
71,756 KB |
testcase_20 | AC | 92 ms
71,756 KB |
testcase_21 | AC | 92 ms
71,512 KB |
testcase_22 | AC | 723 ms
159,980 KB |
testcase_23 | AC | 734 ms
153,604 KB |
testcase_24 | AC | 718 ms
155,000 KB |
testcase_25 | AC | 712 ms
154,528 KB |
testcase_26 | AC | 348 ms
95,996 KB |
testcase_27 | AC | 1,179 ms
169,540 KB |
testcase_28 | AC | 1,208 ms
170,124 KB |
testcase_29 | AC | 1,211 ms
163,008 KB |
testcase_30 | AC | 972 ms
129,616 KB |
testcase_31 | AC | 861 ms
125,424 KB |
testcase_32 | AC | 839 ms
125,012 KB |
testcase_33 | AC | 1,080 ms
181,744 KB |
testcase_34 | AC | 630 ms
129,064 KB |
testcase_35 | AC | 624 ms
158,964 KB |
testcase_36 | AC | 617 ms
157,652 KB |
testcase_37 | AC | 591 ms
167,364 KB |
testcase_38 | AC | 596 ms
168,968 KB |
testcase_39 | AC | 257 ms
91,836 KB |
testcase_40 | AC | 252 ms
91,668 KB |
ソースコード
from collections import deque def DFS(pos): global graph,delete rem=deque([(pos,-1)]) use={pos} while len(rem)>0: now=rem[-1][0] ok=False for i,j in graph[now]: ok=True graph[now].discard((i,j)) if i in use: delete.add(j) while rem[-1][0]!=i: delete.add(rem[-1][1]) use.discard(rem[-1][0]) rem.pop() else: rem.append((i,j)) use.add(i) break if not(ok): use.discard(rem[-1][0]) rem.pop() N,M=map(int,input().split()) graph=[set() for i in range(N)] edge=[] for i in range(M): U,V=map(int,input().split()) edge.append((U,V)) graph[U-1].add((V-1,i)) delete=set() rem=[] for i in range(N): DFS(i) print(N,M-len(delete)) for i in range(M): if i not in delete: print(*edge[i])