1222 信与信封问题

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题解

题目描述 Description

John先生晚上写了n封信，并相应地写了n个信封将信装好，准备寄出。但是，第二天John的儿子Small John将这n封信都拿出了信封。不幸的是，Small John无法将拿出的信正确地装回信封中了。

将Small John所提供的n封信依次编号为1，2，…，n；且n个信封也依次编号为1，2，…，n。假定Small John能提供一组信息：第i封信肯定不是装在信封j中。请编程帮助Small John，尽可能多地将信正确地装回信封。

输入描述 Input Description

n文件的第一行是一个整数n（n≤100）。信和信封依次编号为1，2，…，n。

n接下来的各行中每行有2个数i和j，表示第i封信肯定不是装在第j个信封中。文件最后一行是2个0，表示结束。

输出描述 Output Description

输出文件的各行中每行有2个数i和j，表示第i封信肯定是装在第j个信封中。请按信的编号i从小到大顺序输出。若不能确定正确装入信封的任何信件，则输出“none”。

样例输入 Sample Input

3

1 2

1 3

2 1

0 0

样例输出 Sample Output

1 1

program df;

var i,j,n,m,x,y,z,k,t,tt:longint;

a:array[0..500,0..500] of longint;

b:array[0..100] of boolean;

d,c,e:array[0..100] of longint;

function check(x:longint):boolean;

var i:longint;

begin

for i:=1 to n do

if (a[x,i]<>1) and (not b[i]) then

begin

b[i]:=true;

if (d[i]=0) or (check(d[i])) then

begin

d[i]:=x;

exit(true);

end;

end;

exit(false);

end;

begin

readln(n);

readln(x,y);

while (x<>0) and (y<>0) do

begin

a[x,y]:=1;

readln(x,y);

end;

t:=0;

for i:=1 to n do

begin

fillchar(b,sizeof(b),false);

if check(i) then inc(t); //先将匹配数量求出来

end;

for i:=1 to n do

for j:=1 to n do

if a[i,j]=0 then

begin

a[i,j]:=1; //假设这条边不存在，即i与j是不能匹配

fillchar(d,sizeof(d),0);

tt:=0;

for k:=1 to n do

begin

fillchar(b,sizeof(b),false);

if check(k) then inc(tt);

end;

if tt<>t then //产生了影响，则这条边是肯定的

begin

z:=1;

writeln(i,’ ‘,j);

end;

a[i,j]:=0;

end;

if z<>1 then writeln(‘none’);

end.