???

####程序:
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 条评论

  • @ 2014-10-28 03:59:59

    你这个找拓扑序的程序是O(n^2)的, 当然TLE了. 标准算法应该可以在O(nlogn+m)内找到拓扑序.
    至于为什么WA你自己查查代码.

  • 1

信息

ID
1790
难度
5
分类
图结构 | 拓扑排序数据结构 点击显示
标签
(无)
递交数
981
已通过
303
通过率
31%
被复制
10
上传者