在并查集中可以判断edge所连的两点是否在同一图中，所以每找一条边就少一个图（把两个图合并），所以只找到n-k条边即可
by 静谧时空 @ 2019-07-09 21:21:02
还是不是很明白，是否是我理解题目有误：k棵树之间可以相连？另外上面那张图如何反驳？
by xiaoweiws @ 2019-07-10 08:33:10
上面k是2，打错了...
by xiaoweiws @ 2019-07-10 08:39:23
@[静谧时空](/space/show?uid=61614)
by xiaoweiws @ 2019-07-10 08:39:39
如果一条边所指向的两个点不是在同一图中即find(i)!=find(j)，这时如果选择则这条边就会把两点的集合代表统一（find(i)==find(j)）含有这两个点的两个图就会合并为一个，刚开始有n个点（n个图），没选择一条边就会合并两个图，所以要剩下k只需合并n-k次，我想我解释的应该比较清楚了，~~反正我就是这么理解这题的做法的~~
by 静谧时空 @ 2019-07-10 12:44:05
k棵树之间可以相连？：这我并没有看懂你想表达的到底是什么
另外上面那张图如何反驳？：那张图是合法的
by 静谧时空 @ 2019-07-10 12:45:23
@[xiaoweiws](/space/show?uid=134819)
by 静谧时空 @ 2019-07-10 12:46:27
@[静谧时空](/space/show?uid=61614)
- 噢我想明白了，原来单独一个点也可以算做一颗棉花糖（树，独立的图），之前那张图我以为只有蓝色边连成的树，才一颗树不满足题意；
- 另外理解一下您的思路：对于裸的最小生成树要合并n-1次（对n-1条边操作）得到一个独立的图。因此若想得到k个独立的图就要合并n-k次。
- 多谢dalao
by xiaoweiws @ 2019-07-10 19:19:57
@[xiaoweiws](/space/show?uid=134819) 对，是的
by 静谧时空 @ 2019-07-10 21:33:44
补图
by xiaoweiws @ 2019-07-10 21:47:33