bawang51吧 关注:31贴子:3,169
  • 2回复贴,共1

【OI】TP(topological sort)

只看楼主收藏回复

拓扑排序
var a:array[1..100,1..100]of longint;
b,f:array[1..100]of longint;
i,j,k,n,m,x,y:longint;
begin
readln(n,m);
for i:=1 to m do
begin
readln(x,y);
a[x,y]:=1;
f[y]:=f[y]+1;
end;
i:=0;
while i<n do
begin
j:=1;
while f[j]<>0 do
j:=j+1;
f[j]:=f[j]-1;
for k:=1 to n do
if a[j,k]=1 then
begin
f[k]:=f[k]-1;
a[j,k]:=0;
end;
i:=i+1;
b[i]:=j;
end;
for i:=1 to n do
writeln(b[i]);
end.


IP属地:上海1楼2011-10-18 20:25回复
    无伤版
    var a,link:array[1..100,1..100]of longint;
    b,f:array[1..100]of longint;
    i,j,k,n,m,x,y:longint;
    begin
    readln(n,m);
    for i:=1 to m do
    begin
    readln(x,y);
    a[x,y]:=1;
    f[y]:=f[y]+1;
    end;
    i:=0;
    link:=a;
    while i<n do
    begin
    j:=1;
    while f[j]<>0 do
    j:=j+1;
    f[j]:=f[j]-1;
    for k:=1 to n do
    if link[j,k]=1 then
    begin
    f[k]:=f[k]-1;
    link[j,k]:=0;
    end;
    i:=i+1;
    b[i]:=j;
    end;
    for i:=1 to n do
    writeln(b[i]);
    end.


    IP属地:上海2楼2011-10-18 20:27
    回复
      忽然发现找入度为零的点可以略节省时间一点,当然,时间复杂度不变。
      var a:array[1..100,1..100]of longint;
      f,b:array[1..100]of longint;
      i,j,k,n,m,h,x,y:longint;
      begin
      readln(n,m);
      for i:=1 to m do
      begin
      readln(x,y);
      a[x,y]:=1;
      inc(f[y]);
      end;
      i:=0;
      j:=1;
      while f[j]<>0 do
      j:=j+1;
      h:=j;
      while i<n do
      begin
      j:=h;
      dec(f[j]);
      for k:=1 to n do
      begin
      if a[j,k]=1 then
      begin
      dec(f[k]);
      a[j,k]:=0;
      end;
      if f[k]=0 then
      h:=k;
      end;
      i:=i+1;
      b[i]:=j;
      end;
      for i:=1 to n do
      writeln(b[i]);
      end.
      


      IP属地:上海3楼2011-11-09 15:53
      回复