题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4612
题意：一个包含n个节点m条边的无向连通图（无自环，可能有重边）。求添加一条边后最少剩余的桥的数目。
思路：要想尽可能地消灭桥，那么添加的这条边一定是连通了最多的BCC。
所以首先进行双连通分量分解，并记录桥的数目；然后将同属一个BCC的点缩成一个，代之以block序号，以block序号为点将原图重构为一棵树。
最后求树的直径，桥的数目减去树的直径即为答案。
整体框架是学习了 http://www.cnblogs.com/kuangbin/archive/2013/07/25/3214879.html 的代码。一些细节是自己想的。
学习到的缩点的姿势：在BCC分解后，为每条边是否为桥打上了标记，同时belong数组已记录了每个点所属的连通块号（关节点每次不退栈，而归属于它所找到的最后一个BCC）；这时遍历一遍所有点，如果点 u 所邻接的某条边 i 是桥，那么这条边一定是重构出树中的边，即这条边的终点为 v ，假如用vector<int>形的邻接表 G 存新图，此时应在u和v各自所属的连通块之间加一条边，即G[belong[u]].push_back(belong[v])。
学习到的处理重边的姿势：先把所有边按字典序排序，此时重边必然紧邻，所以addEdge时判一下相邻的边是否相同即可决定这条边是否打重边标记。
这里我用两重while循环、一个flagDup标记以及两个指针cur, i来处理，有点像尺取法：i 与 cur相同的话一直向前走，当遇到第一个 i != cur 时，通过判flagDup来决定当前从开始cur 到 i 之前的边是否打重边标记。开始在边界判断上出了点问题，注意内层循环要保证 i < m。
由于是无向图，同一条边在两个端点各登记一次，所以在边数组里有两个副本，但可以保证两条边的序号仅相差1，这样也可以通过与 1 异或方便地找到另一个副本。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define CLEAR(A, X) memset(A, X, sizeof(A))
#define REP(N) for(int i=0; i<(N); i++)
#define REPE(N) for(int i=1; i<=(N); i++)
#define FREAD(FN) freopen((FN), "r", stdin)
#define pb(a) push_back(a) using namespace std; const int MAX_N = ;
const int MAX_M = ; struct Edge
{
int v, next;
bool isBrg;
bool more;//重边
}edges[MAX_M]; int head[MAX_N], numE;
int low[MAX_N], dfn[MAX_N], S[MAX_N], belong[MAX_N];
int clock, topS;
int block;
bool inStack[MAX_N];
int numBrg; void addEdge(int u, int v, bool isDup){
edges[numE].v = v;
edges[numE].next = head[u];
edges[numE].isBrg = ;
edges[numE].more = isDup;//是否重边
head[u] = numE++; //反向边，序号仅差1
edges[numE].v = u;
edges[numE].next = head[v];
edges[numE].isBrg = ;
edges[numE].more = isDup;
head[v] =numE++;
} void bcc(int u, int p, bool isDup){
low[u] = dfn[u] = ++clock;
S[topS++] = u;
inStack[u] = ;
for(int i=head[u]; i != -; i = edges[i].next){
int v = edges[i].v;
if(v == p && (!isDup)) continue;//parent and no duplicate
if(!dfn[v]){//tree
bcc(v, u, edges[i].more);
low[u] = min(low[u], low[v]);
if(low[v] > dfn[u]){//bridge
numBrg++;
edges[i].isBrg = ;
edges[i^].isBrg = ;
}
}else if(inStack[v])//backward or parent
low[u] = min(low[u], dfn[v]);//include parent
}
if(low[u] == dfn[u]){//new bcc
block++;
int t;
do{
t = S[--topS];
inStack[t] = ;
belong[t] = block;
}while(t != u);
}
} void init(){
numE = ;
numBrg = ;
CLEAR(head, -);
CLEAR(low, ); CLEAR(dfn, );
CLEAR(inStack, );
CLEAR(belong, );
clock = block = topS = ;
} vector<int> G[MAX_N];//缩点后的新图
int dep[MAX_N]; void dfs(int u){
for(int i=; i<G[u].size(); i++){
int v = G[u][i];
if(dep[v] == -){
dep[v] = dep[u]+;
dfs(v);
}
}
} int n, m;
struct Node
{
int u, v;
}nodes[MAX_M];
bool cmp(Node a, Node b){
if(a.u == b.u) return a.v < b.v;
return a.u < b.u;
}
bool same(Node a, Node b){
if(a.u == b.u && a.v == b.v) return true;
return false;
} int main()
{
FREAD("4612.txt");
while(~scanf("%d%d", &n, &m) && n && m){
init();
for(int i=; i<m; i++){
int u, v;
scanf("%d%d", &u, &v);
if(u > v) swap(u, v);
nodes[i].u = u; nodes[i].v = v;
}
sort(nodes, nodes+m, cmp);//将重边聚到一起
int cur = , i = ;
int flagDup = ;
while(cur < m){
while(i<m && same(nodes[cur], nodes[i])){
flagDup = ;//与cur重
i++;
}
if(flagDup) addEdge(nodes[cur].u, nodes[cur].v, );
else addEdge(nodes[cur].u, nodes[cur].v, );
//printf("add edge %d %d\n", nodes[cur].u, nodes[cur].v);
flagDup = ;
cur = i++;
} bcc(, , );//0->1虚拟边
REPE(block) G[i].clear();//block个节点的图
REPE(n){//以block为编号,[1,block]建新图
for(int j=head[i]; j!=-; j=edges[j].next){
if(edges[j].isBrg){
int u = i;
int v = edges[j].v;
G[belong[u]].pb(belong[v]);//缩点
}
}
}
CLEAR(dep, -);
dep[] = ;//以1为根
dfs();
int deepest = , maxDep = -;
REPE(block){//找到最深的
if(dep[i] > dep[deepest]){
maxDep = dep[deepest];
deepest = i;
}
}
CLEAR(dep, -);
dep[deepest] = ;//以deepest为根
dfs(deepest);
int len = ;//树的直径
REPE(block) len = max(len, dep[i]); printf("%d\n", numBrg - len);
}
return ;
}
这道题从MLE改到WA改到RE再改到TLE，最终弃掉自己的版本学习了bin神的。发现他的实现很真实地反映了思路，比如bcc时，增加父节点p和边属性isDup两个参数，这样就通过v!=p && (!isDup)把无重边的父子边过滤掉，剩下真的后向边和有重边的父子边。我在从思路到代码的转换上还需要多加练习。