UVA 10972 RevolC FaeLoN（边-双连通+缩点）-白红宇

UVA 10972 RevolC FaeLoN（边-双连通+缩点）

阅读量：4586 次

发布时间：2019-06-09

本文共 2036 字，大约阅读时间需要 6 分钟。

很好的一道图论题，整整撸了一上午。。。

题意是给定一个无向图，要求将所有边变为有向边，求最少加入多少条有向边，使得该图强连通？这里先假设一个问题：给定一个无向子图，该子图具有怎样的性质才能使得将其无向边都变为有向边后强连通？显然是边-双连通！边连通的性质就是任意两点间存在边部重合的两条路，所以你懂的。。。

所以这个题的解法就是：求出原图的边-双连通分量后缩点，变成一棵bcc树。现在问题就变成了：给定一棵无向树，添加最少边使得该图强连通？这个问题在纸上画画大概能推出来。。。sum为所有叶子节点的个数，ans便是（sum+1）/ 2。。。求边-双连通的方法大白书说的很清楚了，先dfs标记所有桥，然后再dfs1一次，途中不经过桥就行。

还有一点，原图中可能本来就有孤立点（如sample 2中的点10），那么它所在的bcc点的度数为0，所以要在缩点后处理的时候处理一下孤立点。。。

另外还有一点。。。当原图本来就双连通的时候要特判ans=0。。。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #include
                 
                  #define FF(i, a, b) for(int i=a; i
                  
                   =b; i--)#define REP(i, n) for(int i=0; i

G[maxn];vector

edges;inline void init(){ CLR(d, 0); REP(i, n) G[i].clear(); edges.clear();}void add(int u, int v){ edges.PB((Edge){v, 0}); edges.PB((Edge){u, 0}); int nc = edges.size(); G[u].PB(nc-2); G[v].PB(nc-1);}int dfs(int u, int fa){ int lowu = pre[u] = ++dfs_clock; int nc = G[u].size(); REP(i, nc) { int v = edges[G[u][i]].to; if(!pre[v]) { int lowv = dfs(v, u); lowu = min(lowu, lowv); if(lowv > pre[u]) edges[G[u][i]].flag = 1, edges[G[u][i]^1].flag = 1; //标记所有桥 } else if(pre[v] < pre[u] && v != fa) lowu = min(lowu, pre[v]); } return low[u] = lowu;}void dfs1(int u){ bccno[u] = bcc_cnt; int nc = G[u].size(); REP(i, nc) { int v = edges[G[u][i]].to; if(!bccno[v] && edges[G[u][i]].flag != 1) dfs1(v);//不经过桥 }}void find_bcc(){ CLR(pre, 0); CLR(bccno, 0); dfs_clock = bcc_cnt = 0; REP(i, n) if(!pre[i]) dfs(i, -1); REP(i, n) if(!bccno[i]) bcc_cnt++, dfs1(i);}int main(){ while(~scanf("%d%d", &n, &m)) { init(); int ans = 0; REP(i, m) { scanf("%d%d", &u, &v); u--; v--; add(u, v); } find_bcc(); if(bcc_cnt == 1) { puts("0"); continue; } REP(u, n) //缩点 { int nc = G[u].size(); REP(i, nc) { int v = edges[G[u][i]].to; if(bccno[u] != bccno[v]) d[bccno[u]]++; } } FF(i, 1, bcc_cnt+1) { if(d[i] == 0) ans += 2; //孤立点 if(d[i] == 1) ans++; } printf("%d\n", (ans+1)/2); } return 0;}

转载于:https://www.cnblogs.com/dyllove98/p/3241404.html

你可能感兴趣的文章