#FaeLoN

UVA 10972 RevolC FaeLoN(边-双连通+缩点)

很好的一道图论题,整整撸了一上午。。。题意是给定一个无向图,要求将所有边变为有向边,求最少加入多少条有向边,使得该图强连通?这里先假设一个问题:给定一个无向子图,该子图具有怎样的性质才能使得将其无向边都变为有向边后强连通?显然是边-双连通!边连通的性质就是任意两点间存在边部重合的两条路,所以你懂的。。。所以这个题的解法...