这道题算是一个很综合的题目了
题意：已保证给的图是连通图，现在允许你在图中加一条边，使图中的桥的数量最小
思路：首先我们可以去想，桥，如果拆了就会增加一个连通分量。换句话说，桥把整个图分成很多个岛屿一样。
那么，我们能不能把这些岛屿压缩成一个点？那么现在整个图里面就只有一些点，这些点中间的边都是桥
那么问题来了，这个图会有什么特点？
这个图应该是一棵树！因为里面不可能有环。如果存在环，就说明在这个环上，不可能存在桥，但事实上要存在环必然有桥（因为压缩后，整个图里面的边全是桥），所以矛盾了。
所以，我们现在得到了一棵树，里面的边都是桥。继续思考
对于一棵树里面，我们添加一条边，就可能可以形成环。如果成环，那么整个环上面的桥都不会是桥了。
所以，我们只需要在这棵树里面找到最长路，把最长路的首尾相连，整条路上的桥都将不会是桥了！
换句话说，如果桥的数量是Bridge,最长路是line，那么答案就是Bridge - line
好了，整个题目被分成了很多个自题目
如何求桥：http://blog.csdn.net/qwb492859377/article/details/47042473
如何求树中最长路：http://blog.csdn.net/qwb492859377/article/details/47039329
那么怎么岛屿给压缩成一个点？当然通过并查集
在tarjan算法求桥里面，我们知道，如果 lowv > DFN[u] 那么说明边(u,v)是桥。
换句话说 ，如果lowv <= DFN[u],那么这就只是一条普通的边，我们只需要把这样的边的两端在并查集中合并
最后做完求桥之后，把所有的桥枚举，然后清空图，把桥的两端用对应的并查集的编号来代替，这样就把两个模板衔接起来了
注意：Low数组并不能表示岛屿的编号，这里有组反例。
如果对于每个点，遍历边的时候，是按照字典序遍历的
那么，这些点的遍历顺序应该是A 1,B 2,C 3,D 4,E 5,F 6,G 7
所以，刚开始C,D,E对应的Low等于3
后来右边那部分遍历后,B,C,F,G对应的Low等于2
整个岛屿中，Low又有2又有3，所以Low并不能代表岛屿的编号
整个题目大概就是这些需要注意的地方，然后剩下来就只是几个模板的衔接了
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<functional>
#include<algorithm>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 2e5 + 5;
const int INF = 0x3f3f3f3f;int Head[MX], Next[MX], rear;
int Low[MX], DFN[MX], dfs_clock;
int Begin, Bridge;
int P[MX];struct Edge {int u, v, sign;
} E[MX];int find(int x) {return P[x] == x ? x : (P[x] = find(P[x]));
}void Union(int u, int v) {int x = find(u), y = find(v);P[x]=y;
}void find_init(int n){for(int i = 1; i <= n; i++) P[i] = i;
}void edge_init() {rear = 0;memset(Head, -1, sizeof(Head));memset(Next, -1, sizeof(Next));
}void edge_add(int u, int v) {E[rear].u = u;E[rear].v = v;E[rear].sign = false;Next[rear] = Head[u];Head[u] = rear++;
}void tarjan_init() {Bridge = 0;dfs_clock = 0;memset(DFN, 0, sizeof(DFN));
}int tarjan(int u, int from) {Low[u] = DFN[u] = ++dfs_clock;for(int id = Head[u]; ~id; id = Next[id]) {int v = E[id].v;if(!DFN[v]) {int lowv = tarjan(v, u);Low[u] = min(Low[u], lowv);if(lowv > DFN[u]) {E[id].sign = 1;E[id ^ 1].sign = 1;Bridge++;} else {Union(u, v);}} else if(v != from) {Low[u] = min(Low[u], DFN[v]);}}return Low[u];
}int solve(int u, int from, int &ans) {int Max1 = 0, Max2 = 0;for(int id = Head[u]; ~id; id = Next[id]) {int v = E[id].v;if(v == from) continue;int t = solve(v, u, ans) + 1;if(t > Max1) {Max2 = Max1;Max1 = t;} else if(t > Max2) Max2 = t;}ans = max(ans, Max1 + Max2);return Max1;
}int main() {int T, n, m;scanf("%d", &T);while(T--) {edge_init();tarjan_init();scanf("%d%d", &n, &m);find_init(n);for(int i = 1; i <= m; i++) {int u, v;scanf("%d%d", &u, &v);edge_add(u, v);edge_add(v, u);}tarjan(1, -1);int tot = rear;edge_init();for(int i = 0; i < tot; i++) {if(E[i].sign) {int u = find(E[i].u), v = find(E[i].v);edge_add(u, v);Begin = u;}}int ans = 0;if(Bridge) solve(Begin, -1, ans);printf("%d\n", Bridge - ans);}return 0;
}