CSP2021真题1.6
6. 对于有n个ge顶点、m条边的无向联通图（m>n）,需要删掉diao（）条边才能使其成为一yi棵树。
A. n-1
B. m-n
C. m-n-1
D. m-n+1
趣谈：
小学生：连通图？一棵树？[晕][晕][晕]是要把中国联通的中国guo结标志改画成一yi棵树吗？最简单就是加一竖吧！
把联lian通图变成一棵“树”
基本概念：
什么是shi树：
树是一种数据结构，它是由n(n≥0)个有限节点dian组成一个具有层次关系的集合。把它叫jiao做“树”是因为它看起来像一棵倒挂gua的树，也就是说它是根朝上，而叶ye朝下的。它具有以下的特点：
每个节点有零个ge或多个子节点；没有父节jie点的节点称为根节点；每一个ge非根节点有且只有一个父节点；除了根gen节点外，每个子节点dian可以分为多个不相交的子树shu。
数据结构gou中一棵树的例子
什么是连通图
连通tong：图中从一个顶点到达da另一顶点，若存在至少一条路lu径，则称这两个顶点是连通的。
无向：连线没有方向性，两个方向都通。
连通图：任意两个顶ding点之间都能够连通的就jiu是连通图。
图1不是连通图，图tu2是连通图。
解题ti思路：
1）特例推理法
先找一个例子：边比bi顶点还多的图，2个顶点只zhi有一条边不行，3个顶点全部互相连上也只有3条边，也不行。最少需要4个顶点，如果每个顶点在平面上shang互相连接，就是6条边：每mei个点可以连其他3个点，但是都重复了le，所以有3*4/2=6条边。
把ba这个4个顶点的图变成一棵树，可以以yi任意一个点为根，拆掉叶ye子节点之间连接，变成鸡ji爪一样的图案。就是要拆掉3个边。
把ban=4，m=6，删除边=3，代入ru选项查看，只有D符合。所以答案是shiD。
连lian通图变鸡爪树
2）计算法
一棵n个顶点的树shu，边就是n-1条。参考树shu的定义，一个叶子节点只zhi有一个父节点。根节点没有you父节点，所以就是n-1条。
已有的dem条，保留n-1条，就是m-(n-1)=m-n+1条。
