POJ1611The Suspects【并查集】

  • 内容
  • 评论
  • 相关

这里的第一道并查集~


题目点击这里

题目大意:

有一个人(编号为0)感染了SARS,然后一共有M个社团,如果社团中有一个人感染了SARS那么整个社团都会感染SARS,问最后会有多少个人感染了SARS。


题解:

因为这题实际上是合并多个集合,求某个集合元素的数量,那么我们可以考虑使用并查集。

每个社团我们可以让所有人和第一个人合并,期间用一个数组num记录集合的人数,最后找到编号为0那个人的集合有多少人就可以了。


不难不难,代码就当是模版了,加上了一些优化。

var
  f,num:array[0..30000]of longint;
  n,m,i,j,k,p,q:longint;
function gf(x:longint):longint;
begin
  if f[x]=-1 then exit(x);
  f[x]:=gf(f[x]);
  exit(f[x]);
end;
procedure union(p,q:longint);
var
  x,y:longint;
begin
  x:=gf(p);
  y:=gf(q);
  if x=y then exit;
  if num[x]>=num[y] then
  begin
    f[y]:=x;
    num[x]:=num[x]+num[y];
  end
  else begin
    f[x]:=y;
    num[y]:=num[x]+num[y];
  end;
end;
begin
  repeat
    read(n,m);
    if (n=0) and (m=0) then exit;
    fillchar(f,sizeof(f),255);
    fillchar(num,sizeof(num),255);
    for i:=1 to m do
    begin
      read(k);
      read(p);
      for j:=2 to k do
      begin
        read(q);
        union(p,q);
      end;
    end;
    writeln(-num[gf(0)]);
  until false;
end.

这题通过得挺顺利,就没啥可以吐槽的了。。。

评论

0条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据