计算给定无向图中线性生成树的个数

Question

在解决一个在线编码网站的问题时，我遇到了这个问题。在给定的无向图中，是否存在一种算法来找到线性生成树的数量，使得生成树中的每个节点最多有一个子节点?

Answer 1

根据问题，我认为它只是要求找到单线节点的数量。单行是指如果图形

      o
     /
o-o-o-o
      
    o-o-o

那么其中一个线性生成树将是:

      o
     /
o-o-o

要找到这样的树，你可以使用dfs.