結果
問題 |
No.2301 Namorientation
|
ユーザー |
![]() |
提出日時 | 2025-04-09 21:02:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 846 ms / 3,000 ms |
コード長 | 2,753 bytes |
コンパイル時間 | 318 ms |
コンパイル使用メモリ | 82,784 KB |
実行使用メモリ | 239,148 KB |
最終ジャッジ日時 | 2025-04-09 21:05:44 |
合計ジャッジ時間 | 20,928 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
from collections import deque def find(parent, x): if parent[x] != x: parent[x] = find(parent, parent[x]) return parent[x] def union(parent, rank, x, y): x_root = find(parent, x) y_root = find(parent, y) if x_root == y_root: return False if rank[x_root] < rank[y_root]: parent[x_root] = y_root else: parent[y_root] = x_root if rank[x_root] == rank[y_root]: rank[x_root] += 1 return True def find_cycle(n, edges): parent = list(range(n+1)) rank = [1] * (n + 1) back_edge = None st_edges = [] for a, b in edges: if find(parent, a) == find(parent, b): back_edge = (a, b) break else: union(parent, rank, a, b) st_edges.append((a, b)) else: return [] # This case should not happen st_adj = [[] for _ in range(n + 1)] for a, b in st_edges: st_adj[a].append(b) st_adj[b].append(a) a, b = back_edge prev = [None] * (n + 1) q = deque([a]) prev[a] = -1 while q: u = q.popleft() if u == b: break for v in st_adj[u]: if prev[v] is None: prev[v] = u q.append(v) path = [] current = b while current != -1: path.append(current) current = prev[current] path.reverse() return path def main(): import sys input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr +=1 edges = [] adj = [[] for _ in range(N+1)] for _ in range(N): a = int(input[ptr]) b = int(input[ptr+1]) ptr +=2 edges.append((a, b)) adj[a].append(b) adj[b].append(a) cycle_nodes = find_cycle(N, edges) cycle_set = set(cycle_nodes) next_in_cycle = {} len_cycle = len(cycle_nodes) for i in range(len_cycle): u = cycle_nodes[i] v = cycle_nodes[(i+1) % len_cycle] next_in_cycle[u] = v parent = [0] * (N + 1) q = deque() for node in cycle_nodes: parent[node] = -1 q.append(node) while q: u = q.popleft() for v in adj[u]: if parent[v] == 0 and v not in cycle_set: parent[v] = u q.append(v) for a, b in edges: a_cycle = a in cycle_set b_cycle = b in cycle_set if a_cycle and b_cycle: if next_in_cycle.get(a, -1) == b: print("->") else: print("<-") else: if parent[a] == b: print("->") elif parent[b] == a: print("<-") if __name__ == '__main__': main()