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

poj3310 题目链接

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

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

Read more

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条边才能联通,所以最多[……]

Read more