vatsal's blog

Number of rooted trees in an undirected graph
By vatsal, history, 7 years ago, In English

What algorithm should I use to find the number of rooted trees in an undirected graph? This problem requires it

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

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

No, it doesn't. You just need to check if the graph has only one cycle and is connected. It can be done with a simple DFS or with DSU. See here -> 22406598

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

    Can you please prove how you deduced it to the above properties?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Suppose we have a tree with n nodes. Thus, it has n — 1 edges. Now whenever i join an edge between any two nodes in the tree(connect two existing nodes, non adjacent), a cycle of at least 3 nodes will be formed. Thus the new graph should have n edges and has only one component.

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it -21 Vote: I do not like it

    Well, there's another kind of a time consuming way to solve it. First find if a cycle in the graph. Then check if there are no other cycles except the previously found one(run dfs rooted from the nodes from the previously found cycle and test for cycles while not visiting nodes of the previously found cycle) . Finally check if all nodes are in the same component.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I am sorry but while checking my code again I found a bug(fails on some case). The solution is wrong.

      → Reply