分类： 连通分量

题意：求出给定图的生成子图里有多少个是仙人掌。

首先明确生成子图的概念：包括所有的顶点的子图（之前没有弄明白这个一直没有想出来），那么这个操作其实就很简单了，首先判断图形是否为仙人掌，如果是的话把其中所有的圈（其实在这里就是点双联通分量）所包含的边的数量算出来，Π(cnt[i]+1)即为结果（每个圈最多只能去掉一个边）。

首先，判断是否为仙人掌，这个可以利用无向图仙人掌的性质在dfs求双联通分量的时候顺便求出来：对于任意一个dfs树上的节点u，他的反向边数量+他的子节点中low值小于pre[u]的数量<2，如果大于等于2说明这个节点附近已经产生了两个环了，不可能是仙人掌，反之如果所有点都满足这个要求，那么一定是仙人掌。

其次，求每一个圈的边数。这里如果是仙人掌的话，一定每个点双联通分量都是一个圈（否则就会被判定为非仙人掌，所以这里首先保证第一步的正确性是很重要的），这样的话只需要在求点双联通分量时在退栈的时候把每个bcc对应的边的数量记录下来就可以了（注意是边的数量而不是点的）。

最后套一个无聊的高精度板子就ok了，因为格式错误wa了几次。。。UVALive貌似经常有把格式错误当成wa的。。。顺便这个对高精度的要求还挺高，1000位都满足不了开了100000位才过，至于吗呵呵

继续阅读“[图论][双联通分量][无向图仙人掌] UVALive 3514 Cactus”

http://codeforces.com/contest/1013/problem/D

题意：每次可以从矩形的3个角产生第4个角，问至少需要添加多少个方块可以使得让整张图都充满方块。

自己想的是奇怪的思路，因为发现一个联通的块可以扩展到这个块的maxx，maxy，但是之后就不知道怎么做了。看了题解才恍然大悟，原来是把坐标转化成二分图的左右节点，然后考虑连通分量的个数就可以了。证明的时候，首先注意到一点就是二分图中两个点之间的路径个数一定是奇数，对于同一个连通分量中的左右两个点x，y，他们之间的距离如果是1的话那说明二者之间一定有了一条路径了，也就是这个点已经有一个方块了，如果不是1那么至少是3，每次取距离y最近的3个点，按照题目中给的性质，就可以生成一条新的边，也就是从倒数第四个直接联到y，这样的话，每次边的数量都会-2，到最后一定能减少到1，回到之前的情况。所以在同一个连通分量里的左右所有的点一定能连到一起，也就是说所有的方块一定能被涂上。这时候等于说连通分量和能全部染色等价了，我们就只需要计算出来最少需要多少条边使整个图成为连通图就行了。。其实也就是 连通分量数-1

wa点的话因为把n+m写成了2*n错了还以为横纵坐标是一样大的。。。愚蠢的错误emmmm

继续阅读“[二分图][棋盘][连通分量] codeforces Chemical table 1013D”