学步园

思路：求无向图的边双连通 缩点后，求出叶子结点的个数 加1 除2 就是要加的边 （这是个定理，这里就不证明了）

//   
268K   
0MS
#include <stdio.h>
#include <string.h>
#define VM 5010
#define EM 10010

struct E
{
    int
to,nxt;
}edge[2*EM];
int head[VM],vis[VM],dfn[VM],low[VM];
int n,e,cnt;
void addedge (int cu,int cv)
{
    edge[e].to =
cv;
    edge[e].nxt
= head[cu];
    head[cu] = e
++;
}

int min (int a,int b)
{
    return a
> b ? b : a;
}
void dfs (int u,int
fa)   
//Tarjan
{
    vis[u] =
1;
    dfn[u] =
low[u] = ++cnt;
    for (int i =
head[u];i != -1;i  = edge[i].nxt)
    {
       
int v = edge[i].to;
       
if (vis[v] == 1&& v != fa)
           
low[u] = min (low[u],dfn[v]);
       
if (vis[v] == 0)
       
{
           
dfs (v,u);
           
low[u] = min (low[u],low[v]);
       
}
    }
    vis[u] =
2;
}
int main ()
{
    int
m,i,u,v;
    int
deg[VM];
    while
(~scanf ("%d%d",&n,&m))
    {
       
memset (head,0xFF,sizeof (head));
       
memset (vis,0,sizeof(vis));
       
memset (dfn,0,sizeof(dfn));
       
memset (low,0,sizeof(low));
       
memset (deg,0,sizeof(deg));
       
e = 0;
       
while (m -- )
       
{
           
scanf ("%d%d",&u,&v);
           
if (head[u]!= -1 &&edge[head[u]].to
== v)   
//注意有重边，加判断去掉重边
               
continue;
           
addedge (u,v);
           
addedge (v,u);
       
}