race3.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:race3
}

program race3;
const
  maxn=49;
var
  fin,fout:text;
  adj,tmp:array[0..maxn,0..maxn]of boolean;
  unavoid,split:array[1..maxn-1]of boolean;
  unavoids,splits:byte;
  n,i,j:integer;
function connect:boolean;
  var
    q:array[1..maxn+1]of byte;
    v:array[1..maxn-1]of boolean;
    front,rear,i:byte;
  begin
    connect:=true;
    fillchar(v,sizeof(v),0);
    q[1]:=0;
    front:=0;rear:=1;
    repeat
      inc(front);
      if tmp[q[front],n] then exit;
      for i:=1 to n-1 do
        if tmp[q[front],i] and (not v[i]) then begin
          inc(rear);
          q[rear]:=i;
          v[i]:=true;
        end;
    until front=rear;
    connect:=false;
  end;
function issplit(x:byte):boolean;
  var
    q:array[1..maxn+1]of byte;
    v:array[1..maxn-1]of boolean;
    front,rear,i:byte;
  begin
    issplit:=false;
    fillchar(v,sizeof(v),0);
    q[1]:=0;
    front:=0;rear:=1;
    repeat
      inc(front);
      if q[front]<>x then begin
        if adj[q[front],n] then exit;
        for i:=1 to n-1 do
          if (adj[q[front],i] or adj[i,q[front]]) and (not v[i]) then begin
            inc(rear);
            q[rear]:=i;
            v[i]:=true;
          end;
      end;
    until front=rear;
    for i:=1 to rear do
      if adj[x,q[i]] then exit;
    issplit:=true;
  end;
begin
  n:=-1;
  fillchar(adj,sizeof(adj),0);
  assign(fin,'race3.in');
  reset(fin);
  repeat
    read(fin,i);
    if i=-1 then break;
    inc(n);
    while i>-2 do begin
      if n<>i then adj[n,i]:=true;
      read(fin,i);
    end;
  until false;

  fillchar(unavoid,sizeof(unavoid),0);
  unavoids:=0;
  for i:=1 to n-1 do begin
    tmp:=adj;
    for j:=0 to n do begin
      tmp[i,j]:=false;
      tmp[j,i]:=false;
    end;
    if not connect then begin
      inc(unavoids);
      unavoid[i]:=true;
    end;
  end;

  fillchar(split,sizeof(split),0);
  splits:=0;
  for i:=1 to n-1 do
    if unavoid[i] then
      if issplit(i) then begin
        inc(splits);
        split[i]:=true;
      end;

  assign(fout,'race3.out');
  rewrite(fout);
  write(fout,unavoids);
  for i:=1 to n-1 do
    if unavoid[i] then
      write(fout,' ',i);
  writeln(fout);
  write(fout,splits);
  for i:=1 to n-1 do
    if split[i] then
      write(fout,' ',i);
  writeln(fout);
  close(fout);
end.