首页 > 代码库 > 【POJ1144】Network(割点)(模板)
【POJ1144】Network(割点)(模板)
题意:给定一张无向图,求割点个数
思路:感谢CC大神http://ccenjoyyourlife.blog.163.com/的讲解
割点的定义就是某个联通块中删去此点连通性发生变化的的点
有两种割点:1.U为树根,子树个数>1
2.U非树根,有U的子节点V满足low[v]>=dfn[u]表示U的V子树必须通过U去到U的上面
更新时也有两种:dfn[u]<dfn[v]时u--->v 实边 反则u--->v 虚边
实边时low[u]=min(low[u],low[v]) 虚边low[u]=min(low[u],dfn[v])
1 var head,vet,next,low,dfn,b,son,flag:array[1..50000]of longint; 2 n,m,x,i,tot,time,ans:longint; 3 4 procedure add(a,b:longint); 5 begin 6 inc(tot); 7 next[tot]:=head[a]; 8 vet[tot]:=b; 9 head[a]:=tot;10 end;11 12 function min(x,y:longint):longint;13 begin14 if x<y then exit(x);15 exit(y);16 end;17 18 procedure dfs(u:longint);19 var e,v:longint;20 begin21 flag[u]:=1;22 inc(time); low[u]:=time; dfn[u]:=time;23 e:=head[u];24 while e<>0 do25 begin26 v:=vet[e];27 if flag[v]=0 then28 begin29 inc(son[u]);30 dfs(v);31 low[u]:=min(low[u],low[v]);32 if (low[v]>=dfn[u])and(u<>1) then b[u]:=1;33 end34 else low[u]:=min(low[u],dfn[v]);35 e:=next[e];36 end;37 end;38 39 begin40 assign(input,‘1.in‘); reset(input);41 assign(output,‘1.out‘); rewrite(output);42 repeat43 readln(n);44 if n=0 then break;45 fillchar(head,sizeof(head),0);46 fillchar(low,sizeof(low),0);47 fillchar(dfn,sizeof(dfn),0);48 fillchar(flag,sizeof(flag),0);49 fillchar(son,sizeof(son),0);50 fillchar(b,sizeof(b),0);51 repeat52 read(m);53 while not eoln do54 begin55 read(x);56 add(x,m);57 add(m,x);58 end;59 until m=0;60 time:=0;61 for i:=1 to n do62 if flag[i]=0 then dfs(i);63 ans:=0;64 for i:=2 to n do if b[i]=1 then inc(ans);65 if son[1]>1 then inc(ans);66 writeln(ans);67 until n=0;68 close(input);69 close(output);70 end.
【POJ1144】Network(割点)(模板)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。