题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4612
给一个无向图， 加上一条边后，求桥至少有几个；
那我们加的那条边的两个顶点u，v；一定是u,v之间含有桥的数量最多，然后uv之间的桥都没了，剩下的就是要求的结果；
树的直径的定义刚好就是两个节点之间含有最多的边；
下面是有关树的直径的知识；
这个题目需要手动扩展，不然会爆栈，而且手动扩展的话要用C++提交。
代码：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
#define N 200005
int Head1[N], Head2[N], cnt[];
int Stack[N], top, dfn[N], low[N], Time, n, m;
int nBridge, Bridge[N];
int dist[N], vis[N], Max, index;
struct Edge
{
int v, next;
} e1[*N], e2[*N];
void Init()
{
top = nBridge = Time = Max = index = ;
cnt[] = cnt[] = ;
memset(low, , sizeof(low));
memset(dfn, , sizeof(dfn));
memset(Bridge, , sizeof(Bridge));
memset(dist, , sizeof(dist));
memset(Stack, , sizeof(Stack));
memset(Head1, -, sizeof(Head1));
memset(Head2, -, sizeof(Head2));
}
void Add(Edge e[],int Head[], int u, int v, int k)
{
e[cnt[k]].v = v;
e[cnt[k]].next = Head[u];
Head[u] = cnt[k]++;
}
void Tarjar(int u, int father)
{
low[u] = dfn[u] = ++Time;
Stack[top++] = u;
int v, k=;
for(int i=Head1[u]; i!=-; i=e1[i].next)
{
v = e1[i].v;
if(v==father && !k)///避免重边；
{
k++;
continue;
}
if(!dfn[v])
{
Tarjar(v, u);
low[u] = min(low[u], low[v]);
}
else
low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
nBridge++;///可以代表缩点后的节点个数；
while()
{
v = Stack[--top];
Bridge[v] = nBridge;///缩点；
if(u==v)
break;
}
}
}
void bfs(int s)
{
queue<int>Q;
int p, q;
memset(vis, , sizeof(vis));
vis[s] = ;
dist[s] = ;
Q.push(s);
while(!Q.empty())
{
p = Q.front(); Q.pop();
for(int i=Head2[p]; i!=-; i=e2[i].next)
{
q = e2[i].v;
if(!vis[q])
{
vis[q] = ;
dist[q] = dist[p] + ;
Q.push(q);
if(Max<dist[q])
{
Max = dist[q];
index = q;
}
}
}
}
}
int main()
{
int u, v;
while(scanf("%d%d", &n, &m), m + n)
{
Init();
for(int i=; i<=m; i++)
{
scanf("%d%d", &u, &v);
Add(e1, Head1, u, v, );
Add(e1, Head1, v, u, );///原来的树；
}
Tarjar(, );
for(int i=; i<=n; i++)
{
for(int j=Head1[i]; j!=-; j=e1[j].next)
{
int u = Bridge[i];
int v = Bridge[e1[j].v];
if(u != v )
{
Add(e2, Head2, u, v, );
Add(e2, Head2, v, u, );///缩点后的树；
}
}
}
bfs();
bfs(index);///求树的直径的过程；
printf("%d\n", nBridge--Max);///缩点后形成的树每条边都是桥；所以总桥的个数为节点数-1；
}
return ;
}