首页 > 代码库 > 【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(割点)(模板)