题目链接：
点击打开链接
题目大意：
给出一张图，问最少加多少条边，将他变成边双连通图
题目分析：
首先进行点双连通图缩点，（点双连通图一定是边双连通图），然后得到一棵树，，对于一棵树，我们只需要知道树的最底层有多少个点，然后将他们两两连接即可，那么所有的点就至少有两条路径到达，因为树的两条链相连就变成了环，环路就是路径上的点都有两条路径到达，然后很轻易的就能得到结果，缩点什么的早就是模板了
代码如下:
#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <vector>#include <map>#include <stack>#define MAX 1007using namespace std;int n,m,u,v;int dfn[MAX],low[MAX],b[MAX],times,cnt;int in[MAX];typedef pair<int,int> pii;stack<int> s;vector<int> e[MAX];map<pii,bool> mp;void tarjan ( int u , int p ){dfn[u] = low[u] = ++times;s.push ( u );int len = e[u].size();for ( int i = 0 ; i < len ; i++ ){int v = e[u][i];if ( v == p ) continue;if ( !dfn[v] ){tarjan ( v , u );low[u] = min ( low[u] , low[v] );}elselow[u] = min ( low[u] , dfn[v] );}if ( low[u] == dfn[u] ){int temp;do{temp = s.top();b[temp] = cnt;s.pop();}while ( temp != u );cnt++;}}void init ( ){for ( int i = 0 ; i < MAX ; i++ )e[i].clear();while ( !s.empty())s.pop();times = cnt = 0;mp.clear();memset ( in , 0 , sizeof ( in ));}int main ( ){while ( ~scanf ( "%d%d" , &n , &m ) ){init();while ( m– ){scanf ( "%d%d" , &u , &v );e[u].push_back ( v );e[v].push_back ( u );}for ( int i = 1 ; i <= n ; i++ )if ( !dfn[i] ) tarjan ( i ,-1 );for ( int i = 1 ; i <= n ; i++ ){int len = e[i].size();for ( int j = 0 ; j < len ; j++ ){int v = e[i][j];if ( b[i] == b[v] ) continue;if ( mp[make_pair(i,v)] ) continue;mp[make_pair(i,v)] = true;in[b[v]]++;}}int ans = 0;for ( int i = 0 ; i < cnt ; i++ )if ( in[i] == 1 ) ans++;printf ( "%d\n" , (ans+1)/2 );}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
要铭记在心;每天都是一年中最美好的日子
