双连通分量

题意：一个无向图要添加多少条边才能使其变为边双连通分量，和  n 几乎一样的题目，不同的是，poj这题，原图是保证连通的，这题是不连通的，过程完全一样，只是最后计算答案的公式不同.所以题目分析就不写了，直接看poj那题吧，其实这题也是模板题，懂双连通分量的知识的话，并不需要看分析

poj那题，缩点后不会出现孤立点，因为整个图连通的，所以只要找到缩点后的叶子个数就可以了，所以是(leaf+1)/2

对于这题，因为图不连通，可能出现缩点后的孤立点。首先看缩点后的图，可能是一块一块的，对于点数超过1的块，和poj那题是一样的，只要找到叶子，所以没找到一个叶子就计数1，然后连接叶子，就能先把这块变成一个边双连通分量。对于那些只有一个点的块，要向其他块连至少2条边才能保证边双连通，所以找到缩点后有多少个孤立点，这些孤立点要计数2，表示连两条边

最后答案就是(A + 1 + B*2)/2  , A表示有多少个叶子，B表示有多少个孤立点

如果原图就是个边双连通分量，不需要加任何边，输出0

 

同样给出两个代码，第1个代码是简化了tarjan

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define N 1010int n,tot;int dfn[N],low[N],vis[N],de[N],dcnt,bcnt;vector
          
           e[N];void init(){ dcnt = bcnt = 0; for(int i=1; i<=n; i++) { dfn[i] = 0; e[i].clear(); vis[i] = de[i] = 0; }}void dfs(int u ,int fa){ dfn[u] = low[u] = ++dcnt; vis[u] = 1; for(int i=0; i
           
             dfn[u]) //找到一个桥,新增一个连通分量 bcnt++; } else if(vis[v] == 1) //后向边 low[u] = min(low[u] , dfn[v]); }}void solve(){ for(int i=1; i<=n; i++) if(!vis[i]) { dfs(i,-1); bcnt++; } if(bcnt == 1) //整个图本身就是个双连通分量 { cout << 0 << endl; return ; } bool used[N]; memset(used,false,sizeof(used)); for(int i=1; i<=n; i++) { if(e[i].size() == 0) //孤立点，它自身形成一个连通分量 { used[low[i]] = true ; continue; } for(int j=0; j
            
             > n >> tot) { init(); while(tot--) { int u,v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); //偷懒直接用vector建图不用静态链表了 } solve(); } return 0;}
            
           
          
         
        
       
      
     

 

 

模板，找到所有的桥

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;#define N 1010int n,tot;int dfn[N],low[N],ins[N],belong[N],de[N],dcnt,bcnt;vector
           
            e[N];stack
            
             sta;typedef pair
             
               pii;vector
              
               bridge;void init(){ dcnt = bcnt = 0; while(!sta.empty()) sta.pop(); bridge.clear(); for(int i=1; i<=n; i++) { dfn[i] = 0; e[i].clear(); ins[i] = de[i] = 0; }}void dfs(int u ,int fa){ sta.push(u); ins[u] = true; dfn[u] = low[u] = ++dcnt; for(int i=0; i
               
                 dfn[u]) //桥 { bridge.push_back(make_pair(u,v)); ++bcnt; while(true) { int x = sta.top(); sta.pop(); ins[x] = 0; belong[x] = bcnt; if(x == v) break; } } } else if(ins[v]) //后向边 low[u] = min(low[u] , dfn[v]); }}void solve(){ for(int i=1; i<=n; i++) if(!dfn[i]) { dfs(i,-1); bcnt++; while(!sta.empty()) { int x = sta.top(); sta.pop(); ins[x] = 0; belong[x] = bcnt; if(x == i) break; } } if(bcnt == 1) {cout << 0 << endl; return ;} for(int i=0; i
                
                 > n >> tot) { init(); while(tot--) { int u,v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); } solve(); } return 0;}