tyvj p1017
tyvj吧
全部回复
仅看楼主
level 1
2011年06月02日 04点06分 1
level 1
这道题一眼就可以看出用并查集来做
先读入每一对数,将这两对数合并为同一**。
最后查找有几个**。
【参考程序】
program gdfj;
var data:array[1..1000]of longint;
     b:array[1..1000]of boolean;
     n,m,i,j,s,x,y:longint;
procedure initial(a,x:longint);
begin
   data[x]:=a;
end;
function find(x:longint):longint;
begin
   find:=data[x];
end;
procedure merge(a,b:longint);
var i:longint;
begin
   for i:=1 to n do
     if data[i]=b then data[i]:=a;
end;
begin
   fillchar(b,sizeof(b),false);
   for i:=1 to 1000 do
     initial(i,i);
   s:=0;
   readln(n,m);
   for i:=1 to n do
   begin
     readln(x,y);
     if find(x)<>find(y) then
       merge(find(x),find(y));
   end;
   for i:=1 to m do
     b[data[i]]:=true;
   for i:=1 to m do
     if b[i] then inc(s);
   writeln(s);
end.

2011年06月02日 04点06分 2
level 1
2013年05月05日 13点05分 4
1