题意：求最少天几条边，使这个无向图变成双连通图。
/* tarjan缩点后，形成一棵树，求出叶子节点数tot，答案是(tot+1)/2 */ #include<cstdio> #include<cstring> #include<iostream> #define N 1010 using namespace std; int num[N],low[N],instack[N],vis[N],s[N],in[N],belong[N],top,cnt,indexx; int head[N],n,m; struct node { int v,pre; };node e[N*2]; void add(int i,int x,int y) { e[i].v=y; e[i].pre=head[x]; head[x]=i; } void tarjan(int u,int fa) { num[u]=low[u]=++indexx; vis[u]=instack[u]=1; s[++top]=u; for(int i=head[u];i!=-1;i=e[i].pre) if((fa^1)!=i) { int v=e[i].v; if(!vis[v]) { tarjan(v,i); low[u]=min(low[v],num[u]); } else if(instack[v]) low[u]=min(low[v],low[u]); } int x; if(num[u]==low[u]) { ++cnt; do { x=s[top--]; instack[x]=0; belong[x]=cnt; }while(u!=x); } } void work() { for(int i=1;i<=m;i++) { int x,y;scanf("%d%d",&x,&y); add(i*2-2,x,y);add(i*2-1,y,x); } for(int i=1;i<=n;i++) if(!vis[i])tarjan(i,-1); for(int i=1;i<=n;i++) for(int j=head[i];j!=-1;j=e[j].pre) if(belong[i]!=belong[e[j].v]) in[belong[e[j].v]]++; int tot=0; for(int i=1;i<=cnt;i++) if(in[i]==1)tot++; printf("%d ",(tot+1)/2); } int main() { while(scanf("%d%d",&n,&m)!=EOF) { top=cnt=indexx=0; memset(num,0,sizeof(num)); memset(low,0,sizeof(low)); memset(instack,0,sizeof(instack)); memset(vis,0,sizeof(vis)); memset(s,0,sizeof(s)); memset(head,-1,sizeof(head)); memset(e,0,sizeof(e)); memset(in,0,sizeof(in)); memset(belong,0,sizeof(belong)); work(); } return 0; }