边双连通有一个非常简单的做法就是先找出所有桥,然后再dfs一次不走桥即可
答案是(叶子节点的个数+1)/2

 type node=record
next,po:longint;
end; var e:array[..] of node;
p,dfn,low,d,be,fa:array[..] of longint;
hash:array[..,..] of boolean;
b:array[..] of boolean;
len,n,m,x,y,i,ans,t,s,j,h,r:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y:longint);
begin
hash[x,y]:=true;
inc(len);
e[len].po:=y;
e[len].next:=p[x];
p[x]:=len;
end; procedure tarjan(x:longint);
var i,y:longint;
begin
inc(h);
dfn[x]:=h;
low[x]:=h;
i:=p[x];
while i<>- do
begin
y:=e[i].po;
if y<>fa[x] then
begin
if dfn[y]= then
begin
fa[y]:=x;
tarjan(y);
end;
low[x]:=min(low[x],low[y]);
if low[y]>dfn[x] then
begin
b[i]:=true;
b[i xor ]:=true;
end;
end;
i:=e[i].next;
end;
end; procedure dfs(x:longint);
var i,y:longint;
begin
be[x]:=s;
i:=p[x];
while i<>- do
begin
y:=e[i].po;
if (be[y]=) and not b[i] then dfs(y);
if b[i] and (be[x]<>be[y]) then inc(d[be[x]]);
i:=e[i].next;
end;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(n,m);
for i:= to m do
begin
readln(x,y);
if not hash[x,y] then
begin
add(x,y);
add(y,x);
end;
end;
tarjan();
for i:= to n do
if be[i]= then
begin
inc(s);
dfs(i);
end; for i:= to s do
if d[i]= then inc(ans);
writeln((ans+) shr );
end.
05-11 17:22