证一下这个kruskal算法,可能y总觉得挺简单的就没有讲证明。
首先遍历第一条边,cnt+1,这两条边就变成了一棵树,此时数里面有两个点。
然后就是遍历的第二条边,这时有三种情况
1,第二条边与第一条边是相连的,即第二条边有一个点在第一条边上,这时他们构成了同一颗树,这时cnt +1,树里面的点也+1
2,第二条边与第一条边是不相连的。这时有两种结果,第一种就是他们永不相连,这时cnt +1,然后原来树里面的点还是那么多即n + 0。
第二种结果就是他们会在之后的边中相连,这时就涉及到第二条边,都算的话就是cnt+2, n + 2.
3.这两条边已经在一棵树里面了,这时候也在同一个集合中,那么遍历这条边的时候cnt +0, n + 0.
这里枚举了所有情况,第n条边的情况以第二条类推,可以证明树里面每多一个点平均多一个点计数就要加一,即cntn,
只有出现两条边永远不相交时,cnt + 1, n +0。
得证cnt小于n - 1时,永远至少存在一条边与另外一条边永不相交 。
蒙在被子里面自己想出来的,牛逼坏了,插会腰
$ nb \space sto \space orz$
这题要考虑有没有环的情况吗
能形成环的边将不会被并入到集合中
牛逼牛逼