GESP 八级 · GESP 202506 C++ 八级 第 22 题

$n$ 个顶点的无向完全图，有 $n^{n-2}$ 棵生成树。

图的存储方式：邻接矩阵（O(n²)空间，适合稠密图）、邻接表（O(n+m)空间，适合稀疏图）。

有向完全图边数为n(n-1)，无向完全图边数为n(n-1)/2。简单图不含自环和重边。

【考点】生成树计数｜凯莱公式｜图论基础

1. 🎯 考纲定位

本题考查《GESP 考试大纲》图论模块核心结论——凯莱公式（Cayley's Formula）。命题人在此处埋下的是"结论记忆型陷阱"：绝大多数学生能背出"完全图生成树数量是n的n-2次方"，但极少有人理解公式的适用边界。这道题就是在测试：你究竟是真懂，还是只背了个孤立的结论？