bc #73 B || hdu 5631 Rikka with Graph (并查集判断无向图的连通性)

http://acm.hdu.edu.cn/showproblem.php?pid=5631
题意;给出一张n个点n+1(n<=100)条边的无向图,现在删除若干条边(至少一条边),问删完之后图依然联通的方案数。
思路:分析可知,由于只删边,不删点,n个点,最少需要n-1条边才能联通,所以最多删两条边。我们可以暴力枚举删除的两条边(或者一条边) O(n^2)的复杂度完全可以接受。剩下的问题就变成了每次删边之后判断图的连通性。 题解给出的是bfs。。。大概是bfs一遍,然后入队的点数是n就联通? 或者dfs一遍也可以? 也是标记过的点数是n就说明联通? 但是看到排名考前的人都是用到了并查集来判断…比较巧妙。

具体做法是:先把所有的点孤立出来,然后开始添加边,每次union成功(就是添加了一条边)的时候计数器+1,n个点如果能合并n-1次,也就是添加了n-1条有效边(最多也只可能是n-1条,那么说明这n个点之间是联通的。

第一次这样用并查集…憋说话,用心感悟。

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz