pku 3711Redundant Paths_第1页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、pku 3711 redundant paths双连通重量。 题目大意：给出一个连通图，求起码添加多少条边，使得对于随意亮点，不只一条路。即两点间的路去掉一条边还是连通的。 思路：用双联通缩点，然后求出度为一的双连通重量的个数count1，最后(count1+1)/2即是所求！ 这个题基本上算是我接触双连通的第一道题，写了好多个版本，最后还是略微了理解了一些双联通。 双连通重量的tarjan用不用栈都可以，由于它不会存在横向边，不需要考虑下一个点是否在栈中。 if(lowu=nu)count+;dov=s.top();s.pop();visv=0;belongv=count;while(v!=

2、u);用栈的话可以很显然的看出有几个双连通重量（即count），然后某一个点属于某一个双连通重量也很清晰！ vo tarjan(int u,int father) int j,v; dfnu=lowu=cnt+; visitu=1; for(j=headu;j!=-1;j=gej.nt) v=edgej.to; if(v=father) continue; if(!visitv) tarjan(v,u); lowu=min(lowu,lowv); 不用栈的话lowi即是指i所在的双联通重量，比较简洁，不用开无数数组！ 对这道题而言，需要去掉重边。 贴一个比较简洁一点的代码： view code

3、 1 ilude stdio.h 2 include sing.h 3 define n 5005 4 struct node 5 int from,to,next; 6 edgen*4; 7 /bool adjnn; 8 int tol,headn,visitn,dfnn,lown,n,m,cnt,degreen; 9 void a(int a,int b)10 11 edgetol.from=a;edgetol.to=b;edgetol.next=heada;heada=tol+;12 13 int min(int a,int b)14 15 return a b?a:b;16 17 void tarjan(int u,int father)18 19 int j,v;20 dfnu=lowu=cnt+;21 visitu=1;22 for(j=headu;j!=-1;j=edgej.next)23 24 v=edgej.to;25 if(v=father) continue;26 if(!visitv) tarjan(v,u);27 lowu=min(lowu,lowv);28 29 30 int judge(int a,in

人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论