結果
問題 | No.1254 補強への架け橋 |
ユーザー | brthyyjp |
提出日時 | 2020-10-09 23:02:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 332 ms / 2,000 ms |
コード長 | 1,743 bytes |
コンパイル時間 | 308 ms |
コンパイル使用メモリ | 81,584 KB |
実行使用メモリ | 133,696 KB |
最終ジャッジ日時 | 2024-07-20 13:51:20 |
合計ジャッジ時間 | 22,991 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 123 |
ソースコード
def lowlink(g, root=0): n = len(g) order = [n]*n low = [n]*n s = [root] cnt = 0 par = [-1]*n seq = [] while s: v = s.pop() if order[v] != n: continue order[v] = cnt seq.append(v) low[v] = cnt cnt += 1 for u in g[v]: if order[u] < cnt: if par[v] != u: low[v] = min(low[v], order[u]) continue else: par[u] = v s.append(u) child = [[] for _ in range(n)] for v in range(n): if par[v] != -1: child[par[v]].append(v) seq.reverse() for v in seq: for u in child[v]: low[v] = min(low[v], low[u]) # bridge bridge = [] for p in range(n): for c in child[p]: if order[p] < low[c]: bridge.append((p, c)) # articulation points AP = [] for v in range(n): if v == root: if len(child[v]) >= 2: AP.append(v) else: for c in child[v]: if order[v] <= low[c]: AP.append(v) break return AP, bridge import sys import io, os input = sys.stdin.buffer.readline n = int(input()) g = [[] for _ in range(n)] d = {} for i in range(n): a, b = map(int, input().split()) a, b = a-1, b-1 if a > b: a, b = b, a g[a].append(b) g[b].append(a) d[(a, b)] = i #print(d) _, bridge = lowlink(g, 0) s = set() for u, v in bridge: if u > v: u, v = v, u s.add((u, v)) res = [] for k, v in d.items(): if k in s: continue else: res.append(v+1) print(len(res)) print(*res)