結果
問題 |
No.2301 Namorientation
|
ユーザー |
|
提出日時 | 2023-05-18 11:14:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,158 ms / 3,000 ms |
コード長 | 1,340 bytes |
コンパイル時間 | 262 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 364,304 KB |
最終ジャッジ日時 | 2024-12-16 03:23:11 |
合計ジャッジ時間 | 25,583 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
import sys input = sys.stdin.readline from collections import deque INF = float('inf') sys.setrecursionlimit(10**6) def main(): N = int(input()) AB = [] g = [set() for _ in range(N)] for _ in range(N): a, b = map(int, input().split()) a, b = a - 1, b - 1 AB.append((a, b)) g[a].add(b) g[b].add(a) ans = dict() # トポロジカルソート風 vis = [False] * N for i in range(N): if len(g[i]) == 1: que = deque([i]) while que: u = que.popleft() vis[u] = True for v in g[u]: g[v].discard(u) if u < v: ans[(u, v)] = '->' else: ans[(v, u)] = '<-' if len(g[v]) == 1: que.append(v) def dfs(u, prev=-1): for v in g[u]: if v != prev and not vis[v]: if u < v: ans[(u, v)] = '->' else: ans[(v, u)] = '<-' vis[v] = True dfs(v, u) # 残った閉路を処理する for i in range(N): if not vis[i]: dfs(i) # 答え出力 for a, b in AB: print(ans[(a, b)]) main()