結果

問題 No.1254 補強への架け橋
ユーザー lam6er
提出日時 2025-03-31 17:28:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 283 ms / 2,000 ms
コード長 2,440 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 111,780 KB
最終ジャッジ日時 2025-03-31 17:29:52
合計ジャッジ時間 21,003 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 123
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    n = int(stdin.readline())
    edges = []
    for i in range(n):
        a, b = map(int, stdin.readline().split())
        edges.append((a, b))
    
    # Build adjacency list with edge indices
    adj = [[] for _ in range(n + 1)]  # nodes are 1-based
    for idx, (a, b) in enumerate(edges):
        adj[a].append((b, idx))
        adj[b].append((a, idx))
    
    ord_ = [-1] * (n + 1)
    low = [-1] * (n + 1)
    current_ord = 0
    bridges = set()
    
    for v in range(1, n + 1):
        if ord_[v] == -1:
            stack = []
            stack.append((v, -1, -1, False))  # (node, prev_e, parent, is_processed)
            while stack:
                node = stack.pop()
                v, prev_e, parent, is_processed = node
                if not is_processed:
                    if ord_[v] != -1:
                        continue
                    ord_[v] = current_ord
                    low[v] = current_ord
                    current_ord += 1
                    # Push back to process after children
                    stack.append((v, prev_e, parent, True))
                    # Iterate over adjacency list, reversed to process in order
                    for to, e_idx in reversed(adj[v]):
                        if e_idx == prev_e:
                            continue  # skip parent edge
                        if ord_[to] == -1:
                            stack.append((to, e_idx, v, False))
                        else:
                            # Update low for back edge
                            low[v] = min(low[v], ord_[to])
                else:
                    # Post-processing (after children are processed)
                    for to, e_idx in adj[v]:
                        if e_idx == prev_e:
                            continue  # skip parent edge
                        if ord_[to] > ord_[v]:  # child in DFS tree
                            low[v] = min(low[v], low[to])
                            if ord_[v] < low[to]:
                                bridges.add(e_idx)
    
    # Collect non-bridge edges (indices)
    non_bridges = [i + 1 for i in range(n) if i not in bridges]
    non_bridges.sort()
    print(len(non_bridges))
    if non_bridges:
        print(' '.join(map(str, non_bridges)))
    else:
        print()

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