liecow.pas

Magio牛的usaco源代码

{
PROG:liecow
LANG:PASCAL
}

program liecow;
const
  maxn=100;
  maxq=1000;
var
  fin,fout:text;
  g:array[1..maxn,1..maxn]of boolean;
  ans:array[1..maxq,1..3]of integer;
  n,q,liars,liar,a,b,c,i:integer;
function indeg(x:integer):integer;
  var
    i:integer;
  begin
    indeg:=0;
    for i:=1 to n do
      if g[i,x] then inc(indeg);
  end;
function toposort:boolean;
  var
    v:array[1..maxn]of boolean;
    node,i,j:integer;
  begin
    fillchar(v,sizeof(v),0);
    for i:=1 to n do begin
      node:=0;
      for j:=1 to n do
        if (not v[j]) and (indeg(j)=0) then begin
          node:=j;
          v[j]:=true;
          break;
        end;
      if node=0 then begin
        toposort:=false;
        exit;
      end
      else
        for j:=1 to n do
          g[node,j]:=false;
    end;
    toposort:=true;
  end;
begin
  assign(fin,'liecow.in');
  reset(fin);
  readln(fin,n,q);
  for i:=1 to q do begin
    readln(fin,a,b,c);
    ans[i,1]:=a;ans[i,2]:=b;ans[i,3]:=c;
  end;
  close(fin);
  assign(fout,'liecow.out');
  rewrite(fout);

  liars:=0;
  for liar:=1 to n do begin
    fillchar(g,sizeof(g),0);
    for i:=1 to q do
      if ans[i,1]=liar then g[ans[i,3],ans[i,2]]:=true else g[ans[i,2],ans[i,3]]:=true;
    if toposort then inc(liars);
  end;

  writeln(fout,liars);
  close(fout);
end.