這可是第一個并查積的題目哦！
先從問題的簡單做法入手，構造出原始模型。
如果原始模型是對于集合之間合并處理問題，那么就可以使用并查集使得程序變得高效。
并查集的路徑壓縮只有在元素之間的特性存在遞推關系時才可以使用。
關鍵是要理解那兩個調用的函數，以及用樹結構處理時要注意的問題：
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
雪黛依夢 閱讀(306)
評論(0) 編輯 收藏 引用 所屬分類:
并查積