poj 3310 Caterpillar (树的直径+并查集判环+dfs判断连通性)

poj3310 题目链接

题意:给出一个无向图。。。问是否满足。。联通,并且无环,并且能找到一条路径,图中所有的顶点要么在这条路径上,要么与这条路径上的顶点相邻。

思路:一个一个来。。。联通的话任意起点开始跑一遍dfs? 开一个bool数组标记走过的点。。最后扫一遍。。看是否有点没走过

环的话并查集就好。。

关键是第三个条件。。。根据题中题中的例子。。感觉如果存在这样的路径。。。那么这样的路径应该尽可能长?

于是想到求直径。。。然后在bfs的时候顺便记录路径。。。这样我就知道直径是哪些点。。。然后对于所有点。。判断是否在这条直径上或者与之相邻就好。。。

具体做法是。。。开了一个bool数组ok标记直径上的点。。。在存边的时候用一个to[]数组表示相连。。。to[u]=v,to[v]=u…

然后只要ok[i]或者ok[to[i]]满足其一就好。。。

又是1A,蛤蛤蛤蛤蛤,我好神啊(误

 

 

 

 

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个点之间是联通的。

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