dinner.pas

   1 type
   2   leavetype=array [0..500] of boolean;
   3
   4 var
   5   p,q,n,min,i:longint;
   6   know:array [0..500,0..500] of longint;
   7   leave,lea:leavetype;
   8
   9 function deg(i:longint):longint;
  10 var
  11   j:longint;
  12
  13 begin
  14   deg:=0;
  15   for j:=1 to n do
  16     if (not lea[j]) and (know[i,j]=1) then inc(deg);
  17 end;
  18
  19 function connect(i:longint):longint;
  20 var
  21   j:longint;
  22
  23 begin
  24   for j:=1 to n do if (not lea[j]) and (know[i,j]=1) then break;
  25   exit(j);
  26 end;
  27
  28 function noknow:boolean;
  29 var
  30   i,j:longint;
  31
  32 begin
  33   noknow:=true;
  34   for i:=1 to n-1 do
  35     for j:=i+1 to n do
  36       if (know[i,j]=1) and (not (lea[i])) and (not (lea[j])) then exit(false);
  37 end;
  38
  39 function pass(i:longint):boolean;
  40 begin
  41   pass:=true;
  42   if (lea[i]) or (deg(i)=0) then exit(false);
  43 end;
  44
  45 procedure save(p:longint);
  46 begin
  47   leave:=lea;
  48   min:=p;
  49 end;
  50
  51 function done(i:longint):boolean;
  52 var
  53   j:longint;
  54
  55 begin
  56   done:=true;
  57   for j:=1 to n do
  58     if j<>i then
  59       if (know[i,j]=1) and (deg(j)=2) then
  60         if connect(j)<i then exit;
  61   done:=false;
  62 end;
  63
  64 procedure dfs(s:longint);
  65 var
  66   leabak:^leavetype;
  67   i,j,k:longint;
  68
  69 begin
  70   if s>min then exit;
  71   if noknow then begin save(s-1); exit; end;
  72   new(leabak);
  73   leabak^:=lea; k:=0;
  74   i:=0;
  75   repeat
  76     inc(i);
  77     if lea[i] then continue;
  78     j:=deg(i);
  79     if j=1 then
  80       begin
  81         i:=connect(i);
  82         inc(k);
  83         lea[i]:=true;
  84         i:=0;
  85       end
  86     else if j>(n-s-k+1) div 2 then
  87       begin
  88         inc(k);
  89         lea[i]:=true;
  90         i:=0;
  91       end;
  92   until i=n;
  93   if k>0 then
  94     begin
  95       dfs(s+k);
  96       lea:=leabak^;
  97     end
  98   else
  99     for i:=1 to n do
 100       if pass(i) and not done(i) then
 101         begin
 102           lea[i]:=true;
 103           dfs(s+1);
 104           lea[i]:=false;
 105         end;
 106   dispose(leabak);
 107 end;
 108
 109
 110 begin
 111   readln(n);
 112   repeat
 113     readln(p,q);
 114     know[p,q]:=1; know[q,p]:=1;
 115   until (p=0) and (q=0);
 116   min:=n;
 117   dfs(1);
 118   writeln(min);
 119   for p:=1 to n do if leave[p] then write(p,' ');
 120 end.