def find_articulation_points(graph):
_, bccs_by_node = biconnected_component(graph)
return [
u for u, bccs in enumerate(bccs_by_node) if len(bccs) > 1
]def find_articulation_points(graph):
prev = [None] * len(graph)
low = [None] * len(graph)
ret = set()
for source in range(len(graph)):
cur_time = 0
children_count_of_root = 0
for u, is_discovering in tgraph.full_dfs(graph, source, prev=prev):
if is_discovering:
low[u] = cur_time
cur_time += 1
elif (p := prev[u]) != u:
low[u] = min(low[v] for v in graph[u])
if p == source:
children_count_of_root += 1
elif low[u] >= low[p]:
ret.add(p)
if children_count_of_root > 1:
ret.add(source)
return retdef find_articulation_points(graph):
prev = [None] * len(graph)
low = [None] * len(graph)
ret = set()
for source in range(len(graph)):
if prev[source] is not None:
continue
dfs_order = list(dfs(graph, source, prev=prev))
for order, u in enumerate(dfs_order):
low[u] = order
for u in reversed(dfs_order):
if prev[u] != source:
low[u] = min(low[v] for v in graph[u])
if low[u] >= low[prev[u]]:
ret.add(prev[u])
if sum(1 for u in graph[source] if prev[u] == source) > 1:
ret.add(source)
return retdef find_bridges(graph):
prev = [None] * len(graph)
low = [None] * len(graph)
ret = []
for source in range(len(graph)):
cur_time = 0
for u, is_discovering in tgraph.full_dfs(graph, source, prev=prev):
if is_discovering:
low[u] = cur_time
cur_time += 1
elif (p := prev[u]) != u:
if len(graph[u]) == 1:
ret.append((u, p) if u < p else (p, u))
else:
low[u] = min(low[v] for v in graph[u] if v != p)
if low[u] > low[p]:
ret.append((u, p) if u < p else (p, u))
return ret