cansu's blog

By cansu, 9 years ago, In English

How can i find all articulation points in a graph ? What is the easiest way ?

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

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

You mean this?

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

[Edit: I need to remove my code as it is a part of solution of a problem from an ongoing online contest.]

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

    can you describe parent?

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

      When you do DFS on a graph, there will be a DFS tree. The parent of node u is the previous node before you get to u in the DFS tree.

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

        This algorithm doesn't give the correct answer if the graph is biconnected.

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

          Can you give me an example that it doesn't work?

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

          a biconnected graph has no articulation points

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    What should u.low initalised to?