学步园

通过这个题目，学习了下并查集的使用,详细的介绍在《算法导论》上。

并查集有三个基本操作，makeset(建立一个集合),find（找到某个元素所在集合的代表元素）,union（合并两个集合）。

根据启发式策略的不同，在实现上略有差异。

#include <iostream><br /> using namespace std;<br /> struct Node<br /> {<br /> int parent; //指向父节点<br /> int count;//记录以其为代表的集合的元素的个数。union操作时有用,启发式策略。对于该题，可以方便输出最后结果。<br /> };<br /> Node person[30005];<br /> int n,m,k;<br /> int Find(int a) /返回根节点（代表节点）<br /> {<br /> while(person[a].parent!=a) a=person[a].parent;<br /> return a;<br /> }<br /> int Union(int a,int b) //返回根节点（代表节点）<br /> {<br /> while(person[a].parent!=a) a=person[a].parent;<br /> while(person[b].parent!=b) b=person[b].parent;<br /> if(person[a].count>person[b].count)<br /> {<br /> person[b].parent=a;<br /> person[a].count+=person[b].count;<br /> return a;<br /> }<br /> else<br /> {<br /> person[a].parent=b;<br /> person[b].count+=person[a].count;<br /> return b;<br /> }<br /> }<br /> void Init()<br /> {<br /> for(int i=0;i<n;i++)<br /> {<br /> person[i].parent=i;<br /> person[i].count=1;<br /> }<br /> }<br /> int main()<br /> {<br /> int temp,temp2;<br /> while(scanf("%d%d",&n,&m)&&(n!=0||m!=0))<br /> {<br /> Init();<br /> for(int i=0;i<m;i++)<br /> {<br /> scanf("%d",&k);<br /> scanf("%d",&temp);<br /> for(int j=1;j<k;j++)<br /> {<br /> scanf("%d",&temp2);<br /> if(Find(temp)!=Find(temp2)) temp=Union(temp,temp2);<br /> }<br /> }<br /> printf("%d/n",person[Find(0)].count);<br /> }<br /> return 0;<br /> }