题目给的是$10^5$个点的完全图(太多边)
赛中完全没想法
结束后看第二名的代码看会了
题目链接
题意:
给出n,代表有一个n个节点的完全图($\frac {n(n-1)}{2}$条边)
给出m,然后给出m对点,表示给出每一对点之间的边的权重是1
剩余没给出的边的权重是0
求最小生成树
解法:
set把权重为1的边的两个点存进去(当邻接表)
一开始当做没有边,用set把所有的点存进去
从1到n检查是否还在set里面
如果第i个点还在,说明不存在权重为0的边将1到i-1的点和i相连
然后从i这个点开始搜索,所有与i相连 存在路径权重和是0的点 从set里删除
(代表用为0的边将它们连在一起)
(再用一条权重为1的边将刚得到的点集 和之前得到的点集连在一起)
(因为是最小生成树,所以尽量用是0的边)
代码:
1 |
|