这可是第一个并查积的题目哦！
先从问题的简单做法入手，构造出原始模型。
如果原始模型是对于集合之间合并处理问题，那么就可以使用并查集使得程序变得高效。
并查集的路径压缩只有在元素之间的特性存在递推关系时才可以使用。
关键是要理解那两个调用的函数，以及用树结构处理时要注意的问题：
1.合并的时候要注意是将高度较小的树合并到高度较大的树，所以小树的parent指向大树根节点
2.一定要理解一点就是合并两个节点实际上是合并他们的根节点，所以一定要找到节点，找到时候理解好也就是为什么findfather中为什么要用while的原因了
//此题运用并查积：就是将所有的村庄放到一个集合中
#include <iostream>
#include <string>
using namespace std;
struct node
{
int parent;
int height;
};
node village[1000];
//找根节点
int findfather (int a)
{
while ( a != village[a].parent ) //理解while 树状结构：找到最终的跟节点
a = village[a].parent;
return a;
}
//合并到同一集合
void merge (int a, int b)
//注意参数：要合并两个节点的根
{
if ( village[a].height == village[b].height )
{
village[b].parent = a;
village[a].height ++;
}
//小树合并到大树
else if ( village[a].height > village[b].height )
{
village[b].parent = a;
}
else
village[a].parent = b;
}
int main ()
{
int n, m;
while ( scanf ("%d", &n) != EOF && n)
{
for (int i = 1; i <= n; i ++) //根据并查积的算法，先将数组初始化，设定本身为一个独立的集合，并且高度都是 1
{
village[i].parent = i;
village[i].height = 1;
}
scanf ("%d", &m);
int a, b;
int a1, b1;
for (int i = 0; i < m; i ++)
{
scanf ("%d %d", &a, &b); //找出要并入集合的元素的根，如果根节点相同则不并入同一个集合，反之，则并入到同一个集合
a1 = findfather (a);
b1 = findfather (b);
if ( a1 != b1 ) //当根节点不同时合并跟节点
merge (a1, b1);
}
//最后遍历并查积数组看看一共有几个不同的集合
int sum = -1;
for (int i = 1; i <= n; i ++)
{
if ( i == village[i].parent )
sum ++;
}
printf ("%d\n", sum);
}
//system ("pause");
return 0;
}
posted on 2010-08-25 22:48
雪黛依梦 阅读(312)
评论(0) 编辑 收藏 引用 所属分类:
并查积