题面 UVA10972 RevolC FaeLoN Solution 这题就比较牛皮。 我们先来考虑一下图联通的话怎么做。显然，我们可以先把图按边双缩点，边双内部是肯定不用加任何一条有向边就能改成强连通分量的（易证）。 缩完点之后，图一定会变成一颗树。接下来我们依旧可以像这道题那样贪心。我们数一下广义叶子数有多少，要加的边的个数一定为$sum/2$（向上取整）。 连边方式如图所示： 接下来...

题面 UVA610 Street Directions Solution 先来解释一下题面意思：我们现在有一个联通的无向图，我们要把整个图改造为有向图，在保证强连通的情况下使得双向边尽可能少。 我们不妨思考一下：如果一条双向边被我们改造为了单向边，会导致某一个方向上的断开。因此，我们先对原图做边双缩点，桥边是不可能被改造为单向边的（因为改造后直接导致边双间不能互相联通）。 除了桥边之外，其他...

题面 P2860 [USACO06JAN]冗余路径Redundant Paths Solution 首先，我们可以发现题目要求每一个点到其他所有点的路径不只有一条，这本质上就是要我们把这个图所有的桥都消除掉。 要消除掉桥，首先必须要把边双先缩起来。缩边双很简单：和求强连通分量一模一样，唯一要注意的是我们要多记录一个$fa$，防止我们求$low$的时候直接把$fa$算进来。 求完边双之后，我们...

题面 P3225 [HNOI2012]矿场搭建 Solution 这题比较妙。 首先，根据常识，如果一个点爆了，当且仅当它是割点的时候才会影响整个图的连通性。 因此，我们考虑把这道题往点双那方面想。 接下来我们思考这个问题：对于一个点双，我们什么时候需要在它这里面放置逃生通道： 如果与它相连的点双块只有一个：如果爆的是割点，则必须在当前块中的任意点建一个通道；如果爆的是普通点，则当前块则可...

什么是边双？ 双连通分量又分点双连通分量和边双连通分量两种。若一个无向图中的去掉任意一个节点（一条边）都不会改变此图的连通性，即不存在割点（桥），则称作点（边）双连通图。一个无向图中的每一个极大点（边）双连通子图称作此无向图的点（边）双连通分量。求双连通分量可用Tarjan算法。——百度百科 用人话来说，就是在无向图上以边为关键字，对原图缩点 为什么要学边双 与强连通分量类似，我们可以求...