結果

問題 No.1254 補強への架け橋
ユーザー lam6er
提出日時 2025-03-26 15:48:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 318 ms / 2,000 ms
コード長 1,755 bytes
コンパイル時間 163 ms
コンパイル使用メモリ 82,700 KB
実行使用メモリ 113,724 KB
最終ジャッジ日時 2025-03-26 15:49:20
合計ジャッジ時間 22,535 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 123
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    adj = [[] for _ in range(N + 1)]
    for i in range(1, N + 1):
        a, b = map(int, sys.stdin.readline().split())
        adj[a].append((b, i))
        adj[b].append((a, i))
    
    disc = [0] * (N + 1)
    low = [0] * (N + 1)
    visited = [False] * (N + 1)
    bridges = set()
    time = 1
    
    stack = [(1, -1, -1, False, 0)]  # (u, parent, parent_e, is_processed, edge_idx)
    
    while stack:
        u, parent_u, parent_e, is_processed, edge_idx = stack.pop()
        if not is_processed:
            if visited[u]:
                continue
            visited[u] = True
            disc[u] = low[u] = time
            time += 1
            stack.append((u, parent_u, parent_e, True, 0))
            continue
        
        updated = False
        for i in range(edge_idx, len(adj[u])):
            v, e = adj[u][i]
            if v == parent_u:
                continue
            if not visited[v]:
                stack.append((u, parent_u, parent_e, True, i + 1))
                stack.append((v, u, e, False, 0))
                updated = True
                break
            else:
                if disc[v] < disc[u]:
                    low[u] = min(low[u], disc[v])
        
        if not updated:
            if parent_u != -1:
                if low[u] > disc[parent_u]:
                    bridges.add(parent_e)
                low[parent_u] = min(low[parent_u], low[u])
    
    ans = []
    for i in range(1, N + 1):
        if i not in bridges:
            ans.append(i)
    ans.sort()
    print(len(ans))
    if ans:
        print(' '.join(map(str, ans)))
    else:
        print()

if __name__ == "__main__":
    main()
0