针对这个的有很多高效算法,但是——
那些高级的算法先不管,我说说网上一种很简单的算法:
对每个连通块:
1.对图DFS,并建立除系统栈外的一个人工栈,表示DFS每层的顶点
2.如果栈头能够搜到栈中某顶点,则在栈内从此点开始到栈头都是一个环
运用到此题就是继续这样,然后只要发现某一个连通块不简单后直接搜出此连通块剩余部分了事。 |V|∈[0..300]所以不用写人工堆栈。。。
var g:array[1..300,1..300] of boolean;
vis:array[1..300] of boolean;
stack,pos,cycl:array[1..300] of longint;
n,m,a,b,t1,t2,t3,top:longint;
ans:longint;
flag:boolean;
procedure dfs(q:longint);
var w,e:longint;
begin
if flag then begin
for w:=1 to n do
if g[q,w] and not vis[w] then begin
vis[w]:=true;
dfs(w);
end;
end else begin
for w:=1 to n do
if g[q,w] then begin
if vis[w] and not flag then begin
g[q,w]:=false; g[w,q]:=false;
for e:=pos[w] to top do begin
inc(cycl[stack[e]]);
if cycl[stack[e]]>1 then begin
flag:=true;
break;
end;
end;
end;
if not vis[w] then begin
inc(top); stack[top]:=w;
vis[w]:=true; pos[w]:=top;
g[q,w]:=false; g[w,q]:=false;
dfs(w);
end;
end;
end;
end;
begin
readln(n,m);
for a:=1 to m do begin
readln(t1,t2);
g[t1,t2]:=true;
g[t2,t1]:=true;
end;
for a:=1 to n do
if not vis[a] then begin
fillchar(stack,sizeof(stack),0);
top:=1; stack[1]:=a; vis[a]:=true;
pos[a]:=1;
flag:=false;
dfs(a);
if not flag then inc(ans);
end;
writeln(ans);
end.