jzoj 1386. 【2012.02.18普及组】郁闷的记者——拓扑排序

发布于 2019-03-24  9 次阅读


题目描述

你是一个体育报社的记者,你接受到一个艰难的任务:有N支足球队参加足球比赛,现在给你一些比赛的结果,需要你给出各支球队的排名,从1到N。
以下是给你的一些信息:
(1) 没有平局;
(2) 不同的球队排名不能相同;
(3) 对于所有满足1<=a

输入

第一行输入N(1<=N<=5000),表示球队的数量,编号为1到N。第二行输入M(1<=M<=100,000),表示给出的比赛场数,接下来M行,每行两个整数X_i,Y_i,表示X_i能打败Y_i。

输出

输出包含N+1行,前N行描述球队的排名,第i个数表示第i名的球队,第N+1行包含一个整数,如果为0表示不存在其他的排名方法,否则为1表示还有其他的排名方法。

思路

用邻接矩阵记录下每一个点的状态,并用另外两个数组来记录每一个点的出度和入度
枚举每一个点,如果当前点没有入读并且有出度的话就删除这一个点上的所有边,并减掉对应点的出度和入度,如果有两次目标点的入度为0,就说明有多种解法

var
  f:array[0..5000,0..5000] of longint;
  chu,ru,a:array[0..10000] of longint;
  fl:array[0..10000] of boolean;
  i,j,k,n,m,s,x,y,o,bz:longint;
begin
  readln(n);
  readln(m);
  for i:=1 to m do
    begin
      readln(x,y);
      f[x,y]:=1;
      inc(chu[x]);
      inc(ru[y]);
    end;
  o:=1;

  for k:=1 to n do
  for i:=1 to n do
    begin
      if (chu[i]>0) and (ru[i]=0)
        then begin
               bz:=0;
               a[o]:=i;
               inc(o);
               fl[i]:=true;
               for j:=1 to n do
                 if f[i,j]=1 then
                   begin
                     f[i,j]:=0;
                     chu[i]:=chu[i]-1;
                     ru[j]:=ru[j]-1;
                     if ru[j]=0 then inc(bz);
                   end;
               if bz>1 then s:=1;
             end;
    end;
  for i:=1 to o-1 do
    writeln(a[i]);
  for i:=1 to n do
    if fl[i]=false then writeln(i);
  writeln(s);
end.
]]>