首先双连通缩点建立新图（顺带求原图的总的桥数，事实上因为原图是一个强连通图，所以桥就等于缩点后的边）此时得到的图类似树结构，对于新图求一次直径，也就是最长链。我们新建的边就一定是连接这条最长链的首尾，这样就将原图的桥降低了直径个。#include<iostream>#include<cstring&g...

/目录1问题描述2解决方案DescriptionInordertogetfromoneoftheF(1<=F<=5,000)grazingfields(whicharenumbered1..F)toanotherfield,Bessieandtherestoftheherdareforcedtocrossn...

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

/**题目大意:给你一个无向连通图,问加上一条边后得到的图的最少的割边数;算法思想:图的边双连通Tarjan算法+树形DP;即通过Tarjan算法对边双连通缩图,构成一棵树,然后用树形DP求最长链,连接首尾即可;剩下的连通块即为所求答案;算法思路:对图深度优先搜索,定义DFN(u)为u在搜索树中被遍历到的次序号;定义L...