POJ 3352 Road Construction(无向连通图) - c++编程基础

TOP

POJ 3352 Road Construction(无向连通图)

2015-07-20 17:49:00 来源: 作者: 【大中小】浏览:3次

题目地址：POJ 3352

这题就是求最少加多少条边可以使得图为无向双连通图。方法是找度数为1的连通分量，可以只用low来找。然后根据公式（叶子结点数+1）/2即可得到答案。原因是在图中将每两个度数为1的都连起来，度数为2的显然已经可以形成双联通了，因为是无向边，只要加一条，就相当于加了两条有向边，很显然，结果数就是那个公式。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; int head[1200], cnt, index1, ans; int vis[1200], dfn[1200], low[1200], du[1200]; struct node { int u, v, next; }edge[100000]; void add(int u, int v) { edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } void tarjan(int u, int fa) { low[u]=dfn[u]=++index1; vis[u]=1; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(v==fa) continue ; if(!vis[v]) { tarjan(v,u); low[u]=min(low[u],low[v]); } else if(v!=fa) low[u]=min(low[u],dfn[v]); } } void init() { memset(head,-1,sizeof(head)); cnt=0; memset(vis,0,sizeof(vis)); memset(dfn,0,sizeof(dfn)); index1=ans=0; memset(du,0,sizeof(du)); } int main() { int n, m, u, v, i, j; while(scanf("%d%d",&n,&m)!=EOF) { init(); while(m--) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } tarjan(1,-1); for(i=1;i<=n;i++) { for(j=head[i];j!=-1;j=edge[j].next) { int v=edge[j].v; if(low[v]!=low[i]) { du[low[i]]++; } } } for(i=1;i<=n;i++) { if(du[i]==1) ans++; } printf("%d\n",(ans+1)/2); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU 4951 Multiplication table(..	下一篇：POJ 1273 Drainage Ditches （din..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: