不知道在这儿问合不合适，一个图论的问题。。。

我们老师刚讲 我就忘了。。。

【 在 liyus 的大作中提到: 】 : 我们老师刚讲 我就忘了。。。 哇。。。求解。。。[em21]

【 在 Miller 的大作中提到: 】 : : 【 在 liyus 的大作中提到: 】 : : 我们老师刚讲 我就忘了。。。 : ................... 看后半句～

【 在 liyus 的大作中提到: 】 : 看后半句～ 那记不记得大概用啥方法呢？谢谢。。。

Cayley给出完全图生成树的计数公式n^(n-2) 一种简单的证明方法是基于prufer sequence的 prufer sequence:一个长度为n-2的prufer sequence是由1..n的数字组成的序列,允许重复. 这样的序列共有n^(n-2)个 任何一棵有标号的树都可以唯一对应到一个prufer sequence,方法如下: 找到标号最小的叶子节点,输出与它相邻的节点到prufer sequence, 将该叶子节点删去,反复操作,直至剩余2个节点.(zju有2题对应的) http://acm.zju.edu.cn/show_problem.php?pid=1097 http://acm.zju.edu.cn/show_problem.php?pid=1965 反过来,任何一个prufer sequence也可以唯一对应到一棵有标号的树标记所有节点为未删除 依次扫描prufer sequence中的数 比如当前扫描到第k个数u 说明有一个叶子节点连到u,并在当前操作中被删除 找一个标号最小的未被标记为删除的且在prufer sequence第k个位置后未出现过的节点v 在u,v间连边并将v删除 反复操作,最后剩两个节点未被标记为删除,在它们之间连边 显然,这样得到的一个图含有n-1条边,且具有拓扑排序,所以一定是树

thanks! 【 在 liyus 的大作中提到: 】 : Cayley给出完全图生成树的计数公式n^(n-2) 一种简单的证明方法是基于prufer sequence的 prufer sequence:一个长度为n-2的prufer sequence是由1..n的数字组成的序列,允许重复. 这样的序列共有n^(n-2)个 任何一棵有标号的树都可以唯一对应到一个prufer sequence,方法如下: 找到标号最小的叶子节点,输出与它相邻的节点到prufer sequence, 将该叶子节点删去,反复操作,直至剩余2个节点.(zju有2题对应的) http://acm.zju.edu.cn/show_problem.php?pid=1097 http://acm.zju.edu.cn/show_problem.php?pid=1965 反过来,任何一个prufer sequence也? 梢晕ㄒ欢杂Φ揭豢糜斜旰诺氖鞅昙撬薪诘阄瓷境?依次扫描prufer sequence中的数 比如当前扫描到第k个数u 说明有一个叶子节点连到u,并在当前操作中被删除 找一个标号最小的未被标记为删除的且在prufer sequence第k个位置后未出现过的节点v 在u,v间连边并将v删除 反复操作,最后剩两个节点未被标记为删除,在它们之间连边 显然,这样得到的一个图含有n-1条边,且具有拓扑排序,所以一定是树