Road Construction
本来不想做这个题，下午总结的时候发现自己花了一周的时间学连通图却连什么是边双连通不清楚，于是百度了一下相关内容，原来就是一个点到另一个至少有两条不同的路。
题意：给你一副图，求最少需要加几条边使其变为边双连通图。
思路：kuangbin模板上有介绍，这里就不详细说明了。具体做法是tarjan缩点后求度为1（2）的数量ans,答案就是（ans+1）/2。
const int N=1e5+5; struct edge { int to,next,f; } e[N*2]; int ti,c,n,m,top,tot,bridge; int head[N],low[N],dfn[N],belong[N],Stack[N],vis[N],du[N]; void add(int u,int v) { e[tot].to=v; e[tot].next=head[u]; head[u]=tot++; } void init() { bridge=ti=c=top=tot=0; memset(head,-1,sizeof(head)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(vis,0,sizeof(vis)); memset(du,0,sizeof(du)); memset(e,0,sizeof(e)); } void tarjan(int u) { int v; low[u]=dfn[u]=++ti; vis[u]=1; Stack[top++]=u; for(int i=head[u]; i+1; i=e[i].next) { int v=e[i].to; if(e[i].f) continue; e[i].f=e[i^1].f=1; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(vis[v]&&dfn[v]<low[u]) low[u]=dfn[v]; } if(dfn[u]==low[u]) { c++; do { v=Stack[--top]; vis[v]=0; belong[v]=c; } while(v!=u); } } void solve() { for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); int ans=0; for(int i=1; i<=n; i++) for(int j=head[i]; j+1; j=e[j].next) { int v=e[j].to; if(belong[i]!=belong[v]) { du[belong[i]]++; du[belong[v]]++; } } for(int i=1; i<=c; i++) { // printf("%d %d\n",i,du[i]); if(du[i]==2) ans++; } printf("%d\n",(ans+1)/2); } int main() { while(~scanf("%d%d",&n,&m)) { init(); int u,v; while(m--) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } solve(); } return 0; }
