結果

問題 No.2301 Namorientation
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0