难度： 蓝

算法： （边）双联通分量

题意简化： 一张无向图，无重边自环，至少加多少条边使得整个图变为边双连通分量。

先跑一遍边双连通分量，缩点。缩完点之后我们就得到了一个有向无环图。以下文字建立在缩点后的图上。

这道题问至少加多少边。还记得上一讲中有一道类似的题吗？（网络协议）这道题跟那道题不一样的地方就是强连通分量变成了边双连通分量。使用那一题的思想。我们将两个度为 $1$ 的点连起来，消耗一条边。所以答案就是度为 $1$ 的点数的数量除 $2$，向上取整。

注意不用加边的情况。

注意邻接表的使用。

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,vis[5050],ans,pt[5050];
int l[5050],d[5050],s[5050],c,t,br[10050];
int h[10050],ne[10050],to[10050],fr[10050],r=1;
void add(int a,int b){
	fr[++r]=a,to[r]=b;
	ne[r]=h[a];
	h[a]=r;
}
void tarj(int u,int fr){
	d[u]=l[u]=++c;
	for(int i=h[u];i;i=ne[i]){
		int v=to[i];
		if(!d[v]){
			tarj(v,i);
			if(l[v]>d[u]) br[i]=br[i^1]=1;
			l[u]=min(l[u],l[v]);
		}
		else if(i!=(1^fr)) l[u]=min(l[u],d[v]);
	}
}
void dfs(int u){
	s[u]=t;
	for(int i=h[u];i;i=ne[i]){
		int v=to[i];
		if(s[v]||br[i]) continue;
		dfs(v);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}	
	for(int i=1;i<=n;i++){
		if(!d[i]) tarj(i,0);
	}
	for(int i=1;i<=n;i++){
		if(!s[i]){
			t++;
			dfs(i);
		}
	}
	if(t==1){
		printf("0");
		return 0;
	}
	for(int i=2;i<=r;i++){
		int u=fr[i],v=to[i];
		if(s[u]!=s[v]){
			pt[s[v]]++,pt[s[u]]++;
		}
	}
	n=t;
	for(int i=1;i<=n;i++){
		if(pt[i]<=2) ans++;
	}
	printf("%d",(ans+1)/2);
}