結果

問題 No.1254 補強への架け橋
ユーザー shotoyooshotoyoo
提出日時 2020-10-09 22:42:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 595 ms / 2,000 ms
コード長 1,177 bytes
コンパイル時間 161 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 202,668 KB
最終ジャッジ日時 2024-07-20 13:08:00
合計ジャッジ時間 25,156 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 123
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
ns = [[] for _ in range(n)]
d = {}
for ind in range(n):
    i,j = map(lambda x: int(x)-1, input().split())
    ns[i].append(j)
    ns[j].append(i)
    d[min(i,j), max(i,j)] = ind + 1
    
def dfs(i, k, par):
    used[i] = True
    ord[i] = k
    k += 1
    low[i] = ord[i]
    is_aps = False
    count = 0
    for v in ns[i]:
        if not used[v]:
            count += 1
            k = dfs(v, k, i)
            low[i] = min(low[i], low[v])
            if par != -1 and ord[i] <= low[v]:
                is_aps = True
            if ord[i] < low[v]:
                bs.append((min(i, v), max(i, v)))
        elif v!=par:
            low[i] = min(low[i], ord[v])
    if par==-1 and count>=2:
        is_aps = True
    if is_aps:
        aps.append(i)
    return k
used = [False] * n
ord = [False] * n
low = [False] * n
k = 0
aps = []
bs = []
for i in range(n):
    if not used[i]:
        k = dfs(i, k, -1)
ans = set(d.values())
for i,j in bs:
    ans.discard(d[(i,j)])
print(len(ans))
write(" ".join(map(str, ans)))
0