- 拓扑编号
- 2014-10-26 20:54:56 @
####程序:
program topology;
var
q,rd,tp:array[0..10000] of integer;
f:array[1..10000] of boolean;
rear,n,m,i,j,x,y:integer;
a:array[1..10000,1..10000] of integer;
flag:boolean;
begin
readln(n,m);
fillchar(a,sizeof(a),0);fillchar(rd,sizeof(rd),0);
for i:=1 to m do begin readln(x,y);a[x,y]:=1;inc(rd[y]);end;
fillchar(q,sizeof(q),0);fillchar(tp,sizeof(tp),0);
fillchar(f,sizeof(f),true);
rear:=0;
repeat
for i:=1 to n do if f[i] and (rd[i]=0) then break;
x:=i;f[x]:=false;
rear:=rear+1;q[rear]:=x;
flag:=false;
for i:=1 to n do
begin
if (a[x,i]=1) and (rd[i]>0) then begin a[x,i]:=0;dec(rd[i]);end;
flag:=flag or f[i];
end;
until not flag;
for i:=1 to n do write(q[i],' ');writeln;
end.
这题应该就是拓扑排序,但为什么我是WA+TE?
1 条评论
-
doc LV 10 MOD @ 2014-10-28 03:59:59
你这个找拓扑序的程序是O(n^2)的, 当然TLE了. 标准算法应该可以在O(nlogn+m)内找到拓扑序.
至于为什么WA你自己查查代码.
- 1