schlnet.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:schlnet
}

program schlnet;
const
  maxn=100;
var
  fin,fout:text;
  adj:array[1..maxn,1..maxn]of boolean;
  exist:array[1..maxn]of boolean;
  n,i,x,noin,noout:byte;
  noloop:boolean;
function max(a,b:byte):byte;
  begin
    if a>b then max:=a else max:=b;
  end;
procedure findloop(x:byte);
  var
    q,pre:array[1..maxn]of byte;
    v:array[1..maxn]of boolean;
    front,rear,i:byte;
  procedure delloop;
    var
      i:byte;
    begin
      repeat
        for i:=1 to n do begin
          if i=x then continue;
          adj[x,i]:=adj[x,i] or adj[q[front],i];
          adj[i,x]:=adj[i,x] or adj[i,q[front]];
        end;
        exist[q[front]]:=false;
        front:=pre[front];
      until q[front]=x;
      noloop:=false;
    end;
  begin
    fillchar(v,sizeof(v),0);
    q[1]:=x;
    v[x]:=true;
    front:=0;rear:=1;
    repeat
      inc(front);
      for i:=1 to n do
        if exist[i] and adj[q[front],i] then
          if (i=x) and v[i] then begin
            delloop;
            exit;
          end
          else begin
            inc(rear);
            q[rear]:=i;
            pre[rear]:=front;
            v[i]:=true;
          end;
    until front=rear;
    noloop:=true;
  end;
procedure caldeg;
  var
    havein,haveout:array[1..maxn]of boolean;
    i,j:byte;
  begin
    fillchar(havein,sizeof(havein),0);
    fillchar(haveout,sizeof(haveout),0);
    for i:=1 to n do
      if exist[i] then
        for j:=1 to n do
          if exist[j] then
            if adj[i,j] then begin
              haveout[i]:=true;
              havein[j]:=true;
            end;
    noin:=0;noout:=0;
    for i:=1 to n do
      if exist[i] then begin
        if not havein[i] then inc(noin);
        if not haveout[i] then inc(noout);
      end;
  end;
begin
  fillchar(adj,sizeof(adj),0);
  assign(fin,'schlnet.in');
  reset(fin);
  readln(fin,n);
  for i:=1 to n do
    repeat
      read(fin,x);
      if x=0 then break;
      adj[i,x]:=true;
    until false;
  close(fin);

  for i:=1 to n do
    adj[i,i]:=false;

  fillchar(exist,sizeof(exist),1);
  for i:=1 to n do
    if exist[i] then
      repeat
        findloop(i);
      until noloop;

  assign(fout,'schlnet.out');
  rewrite(fout);
  x:=0;
  for i:=1 to n do
    if exist[i] then inc(x);
  if x=1 then begin
    writeln(fout,1);
    writeln(fout,0);
  end
  else begin
    caldeg;
    writeln(fout,noin);
    writeln(fout,max(noin,noout));
  end;
  close(fout);
end.