首页 > 代码库 > POJ 3177 Redundant Paths(Tarjan)
POJ 3177 Redundant Paths(Tarjan)
题目链接
题意 : 一个无向连通图,最少添加几条边使其成为一个边连通分量 。
思路 :先用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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。