Problem Description
N planets are connected by M bidirectional channels that allow instant transportation. It’s always possible to travel between any two planets through these channels.
If we can isolate some planets from others by breaking only one channel , the channel is called a bridge of the transportation system.
People don’t like to be isolated. So they ask what’s the minimal number of bridges they can have if they decide to build a new channel.
Note that there could be more than one channel between two planets.
Input
The input contains multiple cases.
Each case starts with two positive integers N and M , indicating the number of planets and the number of channels.
(2<=N<=200000, 1<=M<=1000000)
Next M lines each contains two positive integers A and B, indicating a channel between planet A and B in the system. Planets are numbered by 1..N.
A line with two integers ‘0’ terminates the input.
Output
For each case, output the minimal number of bridges after building a new channel in a line.
Sample Input
4 4
1 2
1 3
1 4
2 3
0 0
Sample Output
0
题意：给出n个点，m条边。 问：加上一条边使得桥数最少，让你求出该桥数
分析，首先用tarjan 求ebc+求桥的个数+缩点，然后就想添加哪一条边才是可以使更多的桥消失，经过以上操作后的新图特点 是无环的无向图，每一条边都是桥 -所以 ===》其实就是在缩点后的新图 中找到两个点，从一个点到另一个点之间经过最多的点，则 就可以判定 ，连接这两个点就可以得到最少的桥。
答案 ==桥数–树的直径。
ps
（大家懂的，鉴于HDU用的是windows服务器，所以stack大小及其坑爹，稍微深一点的递归栈就会stack overflow。
通常的规避方法是用stack或者手写stack模拟栈的递归过程。这个极其蛋疼啊，而且被卡了STL也很得不偿失唉。（话说这一切都是基于非现场赛来说的，现场赛怎么会卡你这些玩艺儿。）
从Lost（庄立大神）那里学来一种规避栈溢出的方法。
在文件gui头处加上这么一句
#pragma comment(linker, “/STACK:1024000000,1024000000”)//预处理栈大小
后面两个数字随便写。。。你觉得能过就好，另外不要超了栈内存的真正上限。
基于VC++的编译预处理命令，不知道GNU C++上面有没有对应的方式。
去MSDN看一眼就会找到对这一句的对应说明，大概在编译器选项那里。 ）
代码
#pragma comment(linker, "/STACK:1024000000,1024000000")//预处理栈大小 防止爆栈
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#define MAXN 200000+10
#define MAXM 2000000+10
#define INF 100000000
using namespace std;
struct Edge
{int from, to, next;bool cut;//是否为桥
}edge[MAXM];
int head[MAXN], edgenum;
int dfs_clock;//dfs次数 时间戳的 应用
int low[MAXN], dfn[MAXN];
int ebcno[MAXN], ebc_cnt;//ebcno[i]表示i属于哪个EBC ebc_cnt是EBC计数器
int bridge;//桥数
int n, m;//点数 边数
stack<int> S;//存储当前bcc的所有点
bool Instack[MAXN];//标记该点是否在栈里面
vector<int> G[MAXN];//存储缩点后新图
int dist[MAXN];//对新图存储源点的 最长路
bool vis[MAXN];//标记是否查询过
int node;//最长路S - T端点
int ans;//树的直径
void init()
{edgenum = 0;memset(head, -1, sizeof(head));
}
void addEdge(int u, int v)
{Edge E = {u, v, head[u], 0};edge[edgenum] = E;head[u] = edgenum++;
}
void getMap()//建图
{int a, b;while(m--){scanf("%d%d", &a, &b);addEdge(a, b);addEdge(b, a);}
}
void tarjan(int u, int fa)
{int v;low[u] = dfn[u] = ++dfs_clock;//时间戳 S.push(u);Instack[u] = true;//进栈int have = 1;for(int i = head[u]; i != -1; i = edge[i].next){v = edge[i].to;if(have && v == fa)//重边好恶心 因为这里WA 8次 {have = 0;continue;}if(!dfn[v]){tarjan(v, u);low[u] = min(low[u], low[v]);if(low[v] > dfn[u])//桥 {bridge++;edge[i].cut = edge[i^1].cut = true;}}else if(Instack[v])//已搜索过 且 在栈里面 low[u] = min(low[u], dfn[v]);} if(low[u] == dfn[u]) {ebc_cnt++;for(;;)//弹出属于同一个EBC的点 {v = S.top(); S.pop();ebcno[v] = ebc_cnt;//属于当前EBC Instack[v] = false;if(v == u) break; } }
}
void suodian()//缩点 建新图
{for(int i = 1; i <= ebc_cnt; i++) G[i].clear();//初始化 for(int i = 0; i < edgenum; i+=2)//跳过重边 {int u = ebcno[edge[i].from];int v = ebcno[edge[i].to];if(u != v)//不在同一个EBCG[u].push_back(v), G[v].push_back(u); }
}
void find_cut(int l, int r)
{memset(low, 0, sizeof(low));memset(dfn, 0, sizeof(dfn));memset(Instack, false, sizeof(Instack));memset(ebcno, 0, sizeof(ebcno));dfs_clock = ebc_cnt = bridge = 0;for(int i = l; i <= r; i++)if(!dfn[i]) tarjan(i, -1);
}
void BFS(int start)
{queue<int> Q;memset(dist, 0, sizeof(dist));memset(vis, 0, sizeof(vis));node = start;ans = 0;vis[start] = 1;Q.push(start);while(!Q.empty()){int u = Q.front();Q.pop();for(int i = 0; i < G[u].size(); i++){int v = G[u][i];if(!vis[v]){dist[v] = dist[u] + 1;if(dist[v] > ans){ans = dist[v];node = v;} vis[v] = 1; Q.push(v);} }}
}
int main()
{while(scanf("%d%d", &n, &m), n||m){init();getMap();find_cut(1, n);suodian();//缩点 BFS(1);//找最长路 S-T 端点 BFS(node);//最长路 printf("%d\n", bridge - ans);//桥数 - 树的直径 } return 0;
}