题目链接:传送门
题目大意:给你一副无向图，问至少加多少条边使图成为边双联通图
题目思路:tarjan算法+缩点（如果已经是双连通图就直接输出0）
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cctype>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <climits>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define fi first
#define se second
#define ping(x,y) ((x-y)*(x-y))
#define mst(x,y) memset(x,y,sizeof(x))
#define mcp(x,y) memcpy(x,y,sizeof(y))
#define Min(x,y) (x<y?x:y)
#define Max(x,y) (x>y?x:y)
using namespace std;
#define gamma 0.5772156649015328606065120
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define N 11005
#define maxn 5005
typedef long long LL;
typedef pair<int,int> PII; stack<int>sk;
int n,m,hcnt,deep,block,leaf;
int d[maxn],dfn[maxn],low[maxn],head[maxn];
int color[maxn],vis[maxn];
struct Node{
int to,next;
Node(){}
Node(int a,int b):to(a),next(b){}
}node[N<<]; inline void add(int x,int y){
node[hcnt]=Node(y,head[x]);
head[x]=hcnt++;
} inline void init(){
while(!sk.empty())sk.pop();
mst(vis,);
mst(head,-);
mst(d,);
mst(dfn,);
hcnt=deep=;
block=leaf=;
} void dfs(int x,int fa){
int flag=; ///这个不是必要的,有重边时有效
sk.push(x);
vis[x]=;
low[x]=dfn[x]=++deep;
for(int i=head[x];~i;i=node[i].next){
int e=node[i].to;
if(e==fa&&flag){flag=;continue;}
if(vis[e])low[x]=min(low[x],dfn[e]);
else if(!dfn[e]){
dfs(e,x);
low[x]=min(low[x],low[e]);
}
}
if(low[x]==dfn[x]){
++block; ///缩点
int co;
do{
co=sk.top();sk.pop();
vis[co]=;
color[co]=block;
}while(co!=x);
}
} int main(){
int i,j,group,Case=,x,y;
while(scanf("%d%d",&n,&m)!=EOF){
init();
for(i=;i<m;++i){
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
for(i=;i<=n;++i){
if(!dfn[i])dfs(i,-);
}
if(block==){printf("0\n");continue;}
for(i=;i<=n;++i)
for(j=head[i];~j;j=node[j].next){
int e=node[j].to;
if(color[i]!=color[e])
++d[color[i]]; ///d数组保留的是缩点后每个点的度数
}
for(i=;i<=block;++i){
if(d[i]==)leaf+=; ///如果有孤立的点,叶子节点加2
else if(d[i]==)++leaf;
}
printf("%d\n",(leaf+)/);
}
return ;
}