题意：给出一个有n个顶点m条边的无向连通图，问至少添加几条边，使删除任意一条边原图仍连通。
思路：一个边双连通图删除任意一条边仍为连通图。故此题即为求原图添加几条边能成为边双连通图。先对无向图中的强连通分量进行缩点，所有的缩点就能构成一棵树，节点之间的连线即为桥。只需将树中的叶子节点相连，就能构成一个边双连通图。叶子节点即为度为1的连通分量。low[i]值相同的点在同一个连通分量中。所加边数=（叶子数+1)/2;
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int N=1010; 8 struct node 9 {10 int u,v;11 int next;12 } edge[N*2];13 int n,m,cnt,dfs_clock;14 int head[N],degree[N];15 int low[N],dfn[N],vis[N];16 void init()17 {18 cnt = 0;19 dfs_clock = 0;20 memset(head,-1,sizeof(head));21 memset(vis,0,sizeof(vis));22 memset(low,0,sizeof(low));23 memset(dfn,0,sizeof(dfn));24 memset(degree,0,sizeof(degree));25 }26 void add(int u,int v)27 {28 edge[cnt].u = u;29 edge[cnt].v = v;30 edge[cnt].next = head[u];31 head[u] = cnt++;32 }33 void dfs(int u,int father)//简化的无向图Tarjan算法34 {35 vis[u] = 1;36 low[u]=dfn[u]=++dfs_clock;37 for (int i = head[u]; i!=-1; i=edge[i].next)38 {39 int v = edge[i].v;40 if (vis[v]==1&&father!=v)41 {42 low[u] = min(low[u],dfn[v]);43 }44 if (vis[v]==0)45 {46 dfs(v,u);47 low[u] = min(low[u],low[v]);48 }49 }50 vis[u] = 2;51 }52 int main()53 {54 while(~scanf("%d%d",&n,&m))55 {56 int u,v;57 init();58 for (int i = 0; i < m; i++)59 {60 scanf("%d%d",&u,&v);61 add(u,v);62 add(v,u);63 }64 dfs(1,1);//原图是连通的故只需从一个点就能遍历全图65 for (int u = 1; u <= n; u++)66 {67 for (int j = head[u]; j!=-1; j=edge[j].next)68 {69 int v = edge[j].v;70 if (low[u]!=low[v])//点u与点v相连但是不在同一个连通分量中71 {72 degree[low[u]]++;//点u所在的连通分量的度+173 }74 }75 }76 int leaf = 0;77 for (int u = 0; u <= n; u++)78 {79 if (degree[u]==1)80 leaf++;//求叶子节点81 }82 int ans = (leaf+1)/2;83 printf("%d\n",ans);84 }85 return 0;86 }