题目链接：http://poj.org/problem?id=3177
题目大意是一个无向图给你n个点m条边，让你求出最少加多少条边 可以让任意两个点相通两条及以上的路线(每条路线点可以重复，但是每条路径上不能有重边)，简单来说就是让你加最少的边使这个图变成一个双连通图。
首先用tarjan来缩点，可以得到一个新的无环图，要是只有一个强连通分量，那本身就是一个双连通图。要是多个强连通分量，那我们可以考虑缩点后度数为1的点(肯定是由这个点开始连新边最优)，那我们假设数出度数为1的点的个数为cnt，可以画几个图观察可得答案就是(cnt + 1) / 2。但是这题有个问题就是要去掉重边(A B和B A不算重边)，不然会wa...，所以我用了二维map来去重边。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
const int MAXN = ;
map <int , map<int , int> > mp;
struct data {
int next , to;
}edge[MAXN * ];
int head[MAXN] , low[MAXN] , dfn[MAXN] , st[MAXN] , block[MAXN] , du[MAXN];
int top , ord , sccnum , cont;
bool instack[MAXN]; void init() {
memset(head , - , sizeof(head));
memset(instack , false , sizeof(instack));
memset(low , , sizeof(low));
memset(dfn , , sizeof(dfn));
memset(du , , sizeof(du));
top = ord = sccnum = cont = ;
} void add(int u , int v) {
edge[cont].next = head[u];
edge[cont].to = v;
head[u] = cont++;
} void tarjan(int u , int par) {
low[u] = dfn[u] = ++ord;
st[++top] = u;
instack[u] = true;
for(int i = head[u] ; ~i ; i = edge[i].next) {
int v = edge[i].to;
if(v == par)
continue;
if(!dfn[v]) {
tarjan(v , u);
low[u] = min(low[u] , low[v]);
}
else if(instack[v]) {
low[u] = min(low[u] , dfn[v]);
}
}
if(low[u] == dfn[u]) {
int v;
sccnum++;
do {
v = st[top--];
instack[v] = false;
block[v] = sccnum;
}while(u != v);
}
} int main()
{
int n , m , u , v;
while(~scanf("%d %d" , &n , &m)) {
init();
mp.clear();
while(m--) {
scanf("%d %d" , &u , &v);
if(!mp[u][v]) {
add(u , v);
add(v , u);
mp[u][v]++;
}
}
tarjan( , -);
for(int u = ; u <= n ; u++) {
for(int i = head[u] ; ~i ; i = edge[i].next) {
int v = edge[i].to;
if(block[u] != block[v]) {
du[block[u]]++;
}
}
}
int res = ;
for(int i = ; i <= sccnum ; i++) {
if(du[i] == )
res++;
}
printf("%d\n" , (res + ) / );
}
}