POJ3177 Redundant Paths (双联通缩点) - c++编程基础

求对于给定一个连通图，加多少条边可以变成边双连通图。

一个有桥的连通图要变成边双连通图的话，把双连通子图收缩为一个点，形成一颗树。需要加的边为(leaf+1)/2 (leaf为叶子结点个数)。

对于此题，有重边但重边不加入计算。

重边的话，要么在开始去掉，要么用桥来计算入度。

因为桥不属于任何一个边双连通分支，其余的边和每个顶点都属于且只属于一个边双连通分支。对于重边而言，只有一对边被标记为桥，而对于所有重边来言，belong【u】和belong【v】都是不一样的，那么如果用belong【u】！=belong【v】作为添加入度条件的话，毫无疑问会多加的。

这么说的话，缩点重新建图的话，用桥来建更好一点，这样新图就不会有重边。

代码（用桥计算）：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
  
   
#include
   
     #include
    
      #include
      #include
      
        #include
       
         #include
        
          #include
         
           #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rev(i,a,b) for(int i=(a);i>=(b);i--) #define clr(a,x) memset(a,x,sizeof a) #define INF 0x3f3f3f3f typedef long long LL; using namespace std; const int maxn=200005; const int maxm=2000005; struct node { int u,v; bool operator<(const node &b)const { if(b.u!=u)return u
          
           dfn[s]) { bridge++; ecut[e]=ecut[e^1]=1; } } else if(ins[v[e]])low[s]=min(low[s],dfn[v[e]]); } if(low[s]==dfn[s]) { int v; block++; do { v=stck[--top]; ins[v]=false; belong[v]=block; }while(v!=s); } } void solve(int n) { clr(dfn,0); clr(ins,0); indx=block=top=0; for(int i=1;i<=n;i++) if(!dfn[i])tarjan(1,0); } void add_(int a,int b) { u[ecnt]=a; v[ecnt]=b; ecut[ecnt]=0; nex[ecnt]=first[a]; first[a]=ecnt++; } int main() { int a,b; while(~scanf("%d%d",&n,&m)) { ecnt=0; clr(first,-1); for(int i=0;i
           
            
 
             
            代码二： 
             
            #pragma comment(linker, "/STACK:1024000000,1024000000")
#include
             
              
#include
              
                #include
               
                 #include
                 #include
                 
                   #include
                  
                    #include
                   
                     #include
                    
                      #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rev(i,a,b) for(int i=(a);i>=(b);i--) #define clr(a,x) memset(a,x,sizeof a) #define INF 0x3f3f3f3f typedef long long LL; using namespace std; const int maxn=200005; const int maxm=2000005; struct node { int u,v; bool operator<(const node &b)const { if(b.u!=u)return u
                     
                      dfn[s]) { bridge++; ecut[e]=ecut[e^1]=1; } } else if(ins[v[e]])low[s]=min(low[s],dfn[v[e]]); } if(low[s]==dfn[s]) { int v; block++; do { v=stck[--top]; ins[v]=false; belong[v]=block; }while(v!=s); } } void solve(int n) { clr(dfn,0); clr(ins,0); indx=block=top=0; for(int i=1;i<=n;i++) if(!dfn[i])tarjan(1,0); } void add_(int a,int b) { u[ecnt]=a; v[ecnt]=b; ecut[ecnt]=0; nex[ecnt]=first[a]; first[a]=ecnt++; } int main() { int a,b; while(~scanf("%d%d",&n,&m)) { ecnt=0;clr(g,false); clr(first,-1); for(int i=0;i