c++ - 计算给定无向图中线性生成树的数量

Question

在解决其中一个在线编码站点的问题时，我遇到了这个问题。是否有任何算法可以找到给定无向图中线性生成树的数量，使得生成树中的每个节点至多有一个 child ？

Answer 1

根据这个问题，我认为它只是要求查找单行节点的数量。单行是指如果图表是

      o
     /
o-o-o-o
   \   \
    o-o-o

所以线性生成树之一将是:

      o
     /
o-o-o

要找到这样的树，您可以使用 dfs。