不是VIP会员,不能显示答案

题目解答

题目:
(冗余关系)有一篇作文,第一行表示作文中的句子数目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. 
考点: 0
分析: 并查集用模拟来做,原理不变,表述的方式改变。
解答:
评论:
老师: 0