题目链接:传送门
题目大意:给你一副无向图，问至少加多少条边使图成为边双联通图
题目思路: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<<1]; 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,0); mst(head,-1); mst(d,0); mst(dfn,0); hcnt=deep=0; block=leaf=0; } void dfs(int x,int fa){ int flag=1; ///这个不是必要的,有重边时有效 sk.push(x); vis[x]=1; 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=0;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]=0; color[co]=block; }while(co!=x); } } int main(){ int i,j,group,Case=0,x,y; while(scanf("%d%d",&n,&m)!=EOF){ init(); for(i=0;i<m;++i){ scanf("%d%d",&x,&y); add(x,y); add(y,x); } for(i=1;i<=n;++i){ if(!dfn[i])dfs(i,-1); } if(block==1){printf("0 ");continue;} for(i=1;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=1;i<=block;++i){ if(d[i]==0)leaf+=2; ///如果有孤立的点,叶子节点加2 else if(d[i]==1)++leaf; } printf("%d ",(leaf+1)/2); } return 0; }