(冗余关系)有一篇作文,第一行表示作文中的句子数目n 和人物数目m,下面n 句 (每句一行)描述人物关系的句子,描述了m 个人的关系(n<=1000)。每条句子的格式为:X Y。它的意思是:X 认识Y, Y 也认识X。现在要你求出文中冗余关系的数目。注意: 假如A 认识B,B 认识C,则A 也认识C。冗余关系的定义是指:即使没有这条关系,原图的所有关 系照样成立。
例如输入数据为:
3 4
1 4
1 3
4 3
则输出为:1
输出结果说明:共有1 个句子冗余(最后一句)。因为4 和3 的相识关系可从前面两句 推出。请完善下面程序。
const maxnm=1000;
var
n,m,i,j,k,t,tot,tmp:integer;
a:array[1..maxnm] of integer;
begin
readln(n,m);
tot:=0;
for i:=1 to m do
a[i]:=i ;
for k:=1 to n do begin
readln(i,j);
if a[i]=a[j] then
inc(tot) ;
else begin
if a[i]<a[j] then begin
tmp:=a[j];
for t:=1 to m do
if a[t]=tmp then a[t]:=a[i] ;
end
else begin
tmp:=a[i];
for t:=1 to m do
if a[t]=tmp then a[t]:=a[j] ;
end;
end;
end;
writeln(tot);
end.