讨论 / 图论经典例题_求所有环
Hoblovski 2013-05-28 02:57:00
点我顶贴 收藏 删除
话说有一到图论例题是:求图中所有环。

针对这个的有很多高效算法,但是——

那些高级的算法先不管,我说说网上一种很简单的算法:

对每个连通块:

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.

查看更多回复
提交回复