I_LOVE_ROMANIA's blog

Bridges and articulation points
By I_LOVE_ROMANIA, history, 6 years ago, In English

Hey guys! Can anybody explain to me how to find the bridges in a graph? I know how to find the articulation points, but I don't know how to handle the bridges. Also, is there any platform where I can submit these 2 classical algorithms? Thank you in advance!

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

2012-2013 Тренировка СПбГУ B #2 Поиск в глубину

Input format:

n m
u_1 v_1
u_2 v_2
...
u_m v_m

С — bridges

Output format:

bridges_count
edge_id_1
...
edge_id_{bridges_count}

D — articulation points

Output format:

articulation_points_count
vertex_1
...
vertex_{articulation_points_count}
→ Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Here's a nice explanation for it: https://cp-algorithms.com/graph/bridge-searching.html

→ Reply