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

Number of rooted trees in an undirected graph
Автор vatsal, история, 8 лет назад, По-английски

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

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

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

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

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится -21 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить