题解 P1992 【不想兜圈的老爷爷】

kkksc03 · 2013-12-21 22:38:25 · 题解

模型基础：判断有向图是否有环（回路）

[算法分析]

搜索 <=70 分

拓扑 100分

显然：出图结点 < 图上结点 && 余下结点入度 > 零 即可判断为有环（回路）

时间复杂度：O(n^2)

[标程]

Program usqwedf_bxdqdlyy;
var
 n,m,i,x,y,k,h,find,t,base:longint;
 g,in_to,p:array[0..1001] of longint;
 map:array[0..1001,0..1001] of longint;
begin
  readln(n,m,base);
  for i:=1 to m do begin
　　  readln(x,y);
    in_to[y]:=in_to[y]+1; g[x]:=g[x]+1; map[x,g[x]]:=y;
  end;
　 while True do begin
    h:=0;
    for i:=1 to n do begin 
　　　  if in_to[i]=0 then begin
　　　    in_to[i]:=-1;
　　　　  h:=h+1; p[h]:=i; 
　　    end;
    end;
    find:=find+h;
    if h=0 then break;
    if find=n then break;
    for i:=1 to h do
      for k:=1 to g[p[i]] do in_to[map[p[i],k]]:=in_to[map[p[i],k]]-1;
  end;
　 if find=n then begin
    writeln('Yes');
    base:=2; t:=1;
    while k>0 do begin
      if k and 1=1 then t:=t*base mod 9997;
      base:=base*base mod 9997;
      k:=k>>1;
　　 end;
    writeln(t);
  end
  else begin 
    writeln('No');
    writeln(base*base);
  end;
end.
kkksc03注：亦可使用tarjan缩点。