Блог пользователя I_LOVE_ROMANIA

Bridges and articulation points
Автор I_LOVE_ROMANIA, история, 6 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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}
→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

→ Ответить