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.
这题通过得挺顺利,就没啥可以吐槽的了。。。
发表回复