結果
問題 |
No.1553 Lovely City
|
ユーザー |
![]() |
提出日時 | 2023-12-01 12:46:06 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,433 bytes |
コンパイル時間 | 563 ms |
コンパイル使用メモリ | 82,244 KB |
実行使用メモリ | 269,740 KB |
最終ジャッジ日時 | 2024-09-26 15:17:55 |
合計ジャッジ時間 | 5,197 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | TLE * 1 -- * 25 |
ソースコード
import sys input = sys.stdin.readline from heapq import * def topsort(G): Q = [] count = [0] * len(G) for u in range(len(G)): for v in G[u]: count[v] += 1 for u in range(len(G)): if count[u] == 0: heappush(Q, u) anslst = [] while Q: u = heappop(Q) anslst.append(u) temp = [] for v in G[u]: count[v] -= 1 if count[v] == 0: heappush(Q, v) return anslst N, M = map(int, input().split()) G = [[] for i in range(N)] for i in range(M): u, v = map(int, input().split()) u, v = u - 1, v - 1 G[u].append(v) def non_rec_dfs(s): stack = [] stack.append(s) par = [-1] * N while stack: u = stack.pop() seen[u] = 1 if u >= 0: stack.append(~u) for v in G[u]: if v == par[u] or seen[v]: continue par[v] = u stack.append(v) else: u = ~u if par[u] != -1: ans2.append((par[u] + 1, u + 1)) return ans2 ans = topsort(G) seen = [0] * N if len(ans) == N: ans2 = [] for a in ans: if seen[a]: continue non_rec_dfs(a) print(len(ans2)) for a, b in ans2: print(a, b) else: print(N) for i in range(N-1): print(i+1, i+2) print(N, 1)