首页 > 代码库 > POJ 3177 Redundant Paths（Tarjan）

POJ 3177 Redundant Paths（Tarjan）

2024-07-18 15:16:03   227人阅读

题目链接

题意 ： 一个无向连通图，最少添加几条边使其成为一个边连通分量 。

思路 ：先用Tarjan缩点，缩点之后的图一定是一棵树，边连通度为1。然后找到所有叶子节点，即度数为1的节点的个数leaf，最后要添加的边的条数就是（leaf+1）/2 ；

 1 // 3177 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6  7 using namespace std ; 8  9 int head[101010],fb[101010],low[101010],dfn[101010] ,degree[101010];10 int cnt,timee ,ans ;11 struct node12 {13     int u ;14     int v ;15     int next ;16 }p[101010];17 18 void tarjan(int u)19 {20     dfn[u] = low[u] = ++timee  ;21     for(int i = head[u] ; i != -1 ; i = p[i].next)22     {23         int v = p[i].v ;24         if(fb[i^1]) continue ;25         fb[i] = 1 ;26         if(dfn[v])  low[u] = min(low[u],dfn[v]) ;27         else28         {29             tarjan(v) ;30             low[u] = min(low[v],low[u]) ;31             //if(low[v] > dfn[u])32             //    ans /++ ;33         }34     }35 }36 void Init()37 {38     cnt = timee = ans = 0 ;39     memset(head,-1,sizeof(head)) ;40     memset(dfn,0,sizeof(dfn)) ;41     memset(low,0,sizeof(low)) ;42     memset(fb,0,sizeof(fb)) ;43     memset(degree,0,sizeof(degree)) ;44 }45 void addedge(int u,int v)46 {47     p[cnt].u = u ;48     p[cnt].v = v ;49     p[cnt].next = head[u] ;50     head[u] = cnt ++ ;51     p[cnt].u = v ;52     p[cnt].v = u ;53     p[cnt].next = head[v] ;54     head[v] = cnt ++ ;55 }56 int main()57 {58     int F,R ;59     while(scanf("%d %d",&F,&R) != EOF)60     {61         Init() ;62         int x,y ;63         for(int i = 0 ; i < R ; i++)64         {65             scanf("%d %d",&x,&y) ;66             addedge(x-1,y-1) ;67         }68         tarjan(0) ;69         for(int i = 0 ; i < F ; i++)70         {71             for(int j = head[i] ; j != -1 ; j = p[j].next)72             {73                 if(low[i] != low[p[j].v])74                     degree[low[i]] ++ ;75                 76             }77         }78         for(int i = 1 ; i <= F ; i ++)//  时间戳是从1开始的，所以low的值是可以到达F的，79             if(degree[i] == 1)80             ans ++ ;81         printf("%d\n",(ans + 1)/2) ;82     }83     return 0 ;84 }
View Code

 


联系
我们