Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

How to form bridge tree if bridges are given?
Автор Mikemirzyanov1, история, 4 года назад, По-английски

Can someone share the details to construct the bridge tree provided we have the bridges? I have already seen the quora link for bridge tree but cannot understand as it uses edge list representation of graph which I don't know.

I know how to find bridges and need to perform dfs on the bridge tree, but how to construct it. Someone please help.

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

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

1) Remove these bridges from the graph

2) Find connected components using the remaining (non bridge) edges using dsu or dfs or whatever you like.

3) Treat each connected component as a node, and for each bridge add an edge between the two components that it connects.

→ Ответить