rachitiitr's blog

Finding biconnected components in an undirected graph
By rachitiitr, history, 9 years ago, In English

The following problem deals with finding the biconnected components in an Undirected graph and treating them as vertices. The code provided in editorial isn't easy for me to understand. Can someone share a template code for how to find biconnected components?
The code given on GeeksforGeeks finds the edges in a biconnected component. I do not trust it as in the solution given there, he talks about cross-edge and stuff. Cross-edge in undirected graph?
Link to the Problem --> Problem E. Pursuit For Artifacts

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rachitiitr (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

This problem deals with edge biconnected components. They are described very well in this blog by Baba

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So edge biconnected components mean bridge components as per his definition?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Thanks btw the code link you have mentioned in your tutorial on Mo's Algorithm on Trees has been blocked. You should update it now.

        → Reply