题目的意思很简单，给你一个已经连通的无向图，我们知道，图上不同的边连通分量之间有一定数量的桥，题目要求的就是要你再在这个图上加一条边，使得图的桥数目减到最少。
首先要做的就是找出桥，以及每个点所各自代表的连通分量。 找桥的方法就是经典的low[u],pre[v]的判断，这个在大白书上也有比较详尽的介绍。当我们找到桥之后我们当然要把桥边存起来，存的时候就有很多姿势了，因为题目给的点达到200000的级别，所以肯定不能开一个邻接矩阵，所以存的时候要么就开个vector<Edge>存下所有的桥边，但是遍历索引的时候就会很蛋疼。要么就采用另外一种方法，vector<int> P[i],其中P[i]这个vector里存下了所有的与i相连构成桥边的点，也就是P[i][j]和i之间存在桥。
找完桥之后就是找边双连通分量。按照大白书上的说法，第一遍dfs找桥，第二遍dfs只需要跳过所有的桥边dfs就可以找到属于同一个边双连通分量的点了。所以当你要判断由u能不能dfs到v的时候，只需要判断(u,v) 是不是桥，也就是v在不在P[i]里，在的话则跳过。
当我们做完上述操作的时候，我们就可以求出了各自点代表的连通分量了。这个时候我们就重新缩点构图，处于同一个边双连通分量内的点缩成一个点，那么最后什么边会是新图上的边呢？ 根据性质我们可以知道，只有桥才是新图上的边，这个时候我们存储的P[i]就派上大用途了，因为P[i][j]和i各自处于的双连通分量中存在边，所以根据P数组和bccno就可以建出新的图。
建出新的图之后就是关于如何实现减少桥边的问题了。不难发现，当前的图是一棵树（这是自然的吧），所以树上的每一条边都是桥，当我们加了一条边之后，就会形成环，这个环所在的所有点这时候又缩成一个点，换言之，环上的桥边减少了。显然我们要选的就是新图上最长的链。
树的最长链就是树的直径。找直径的方法可以考虑采取树dp（我之前的挫办法），也可以用两次BFS,随便选一个点BFS,BFS到的最后一个点一定是直径的一端，然后再从这个点BFS,BFS到的最后一个点必然也是直径的一端。但是BFS写起来没有DFS版本的快，DFS就是随便选一点dfs,dfs到的深度最大的点是直径的一端，从那一个点再dfs一次，深度最大的那个点就是直径的另一端，这时这个点的深度dep-1就是最长链的长度。
最后输出的答案就是桥的数量－最长链的长度，桥的数量就是树的点－1 也就是 bcc_cnt-1, 最长链的长度是dep-1,所以最后的答案就是bcc_cnt-dep
下面的代码严重的参(chao)考(xi)了这个网址，感谢大神们的博客让我得到长足的进步：
http://www.cnblogs.com/arbitrary/archive/2013/08/04/3236092.html
#pragma warning(disable:4996)
#pragma comment(linker,"/STACK:102400000,102400000")
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<iostream>
#define maxn 200050
using namespace std;
struct Edge
{
int u, v;
Edge(){}
Edge(int ui, int vi) :u(ui), v(vi){}
};
vector<int> G[maxn+50];
vector<Edge> edges;
vector<int> P[maxn + 50]; // 桥点邻接表
int n,m;
int low[maxn + 50];
int pre[maxn + 50];
int dfs_clock;
int dfs(int u, int fa)
{
int lowu = pre[u] = ++dfs_clock;
for (int i = 0; i < G[u].size(); i++){
int mm = G[u][i];
if (fa == (mm ^ 1)) continue;
int v = edges[mm].v;
if (!pre[v]){
int lowv = dfs(v, mm);
lowu = min(lowu, lowv);
if (lowv>pre[u]){
P[u].push_back(v);
P[v].push_back(u);
}
}
else if (pre[v] < pre[u]){
lowu = min(lowu, pre[v]);
}
}
return low[u] = lowu;
}
int bccno[maxn + 50];
int bcc_cnt;
void dfs_bcc(int u)
{
bccno[u] = bcc_cnt;
for (int i = 0; i < G[u].size(); i++){
int mm = G[u][i];
int v = edges[mm].v;
if (bccno[v]) continue;
bool flag = true;
for (int j = 0; j < P[u].size(); j++){
if (v == P[u][j]) {
flag = false;
break;
}
}
if (!flag) continue;
dfs_bcc(v);
}
}
void find_bcc()
{
memset(low, 0, sizeof(low));
memset(pre, 0, sizeof(pre));
dfs_clock = 0;
memset(bccno, 0, sizeof(bccno));
bcc_cnt = 0;
for (int i = 1; i <= n; i++){
if (!pre[i]) dfs(i, -1);
}
for (int i = 1; i <= n; i++){
if (!bccno[i]){
bcc_cnt++;
dfs_bcc(i);
}
}
}
vector<int> NG[maxn + 50];
int dep[maxn + 50];
void ndfs(int u, int depth)
{
dep[u] = depth;
for (int i = 0; i < NG[u].size(); i++){
int v = NG[u][i];
if (!dep[v]) ndfs(v, depth + 1);
}
}
void constructNG()
{
for (int i = 0; i <= bcc_cnt; i++){
NG[i].clear();
}
for (int i = 1; i <= n; i++){
for (int j = 0; j < P[i].size(); j++){
int v = P[i][j];
NG[bccno[i]].push_back(bccno[v]);
}
}
}
int main()
{
while (cin >> n >> m&&(n||m))
{
for (int i = 0; i <= n; i++) G[i].clear(), P[i].clear();
edges.clear();
int u, v;
for (int i = 0; i < m; i++){
scanf("%d%d", &u, &v);
edges.push_back(Edge(u, v));
G[u].push_back(edges.size() - 1);
edges.push_back(Edge(v, u));
G[v].push_back(edges.size() - 1);
}
find_bcc();
constructNG();
memset(dep, 0, sizeof(dep));
ndfs(1, 1);
int mxdep = 0; int mdp=0;
for (int i = 1; i <= bcc_cnt; i++){
if (dep[i] > mxdep){
mdp = i; mxdep = dep[i];
}
}
memset(dep, 0, sizeof(dep));
ndfs(mdp, 1);
mxdep = 0;
for (int i = 1; i <= bcc_cnt; i++){
if (dep[i] > mxdep) mxdep = dep[i];
}
printf("%d
", bcc_cnt-mxdep);
}
return 0;
}