hdu1232(并查集)

關于并查集，最主要的是是這樣的一張圖

也就是維護與查詢集合。

而為了加快查詢查詢，可以進行的就是将上圖的左集合變換為右集合，稱之為壓縮路徑。

因為我們隻想知道該元素是否屬于某集合，是以路徑壓縮雖然改變了元素的前驅，但是保留的是父節點，也就是頂點。

我們考慮單鍊的情況，如果存在單鍊如圖

那麼通過優化，可得

如果元素多了之後，查詢兩元素是否屬于同一集合，則可以将O(n)的複雜度降為O(1)，這樣對于多次查詢的情況，可以極大提高效率。

以HDU1232為例，代碼如下

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int pre[1050];

int Find(int x) //已優化
{
    int r = x;
    while(pre[r] != r)
        r = pre[r];
    int i = x, j;
    while (i != r)
    {
        j = pre[i];
        pre[i] = r;
        i = j;
    }
    return r;
}

void Join(int x, int y)
{
    int fx = Find(x), fy = Find(y);
    if (fx != fy)
        pre[fx] = fy;
}

int main()
{
    int n, m;
    while (scanf("%d%d", &n, &m) && n)
    {
        for (int i = 1; i <= n; i++)
            pre[i] = i;
        for (int i = 0; i < m; i++)
        {
            int s, e;
            scanf("%d%d", &s, &e);
            Join(s, e);
        }
        int ans = 0;
        for (int i = 1; i <= n; i++)
            if (pre[i] == i)
                ans++;
        printf("%d\n", ans - 1);
    }
    return 0;
}
           

其中

Find函數為查詢元素x，并傳回父元素r。代碼裡的是已經進行了路徑壓縮後的查詢函數。

Join函數為合并元素，将x與y合并，置入一個集合。

集合的初始化我寫到了main函數裡，是這兩句代碼

for (int i = 1; i <= n; i++)
            pre[i] = i;
           

可以單獨提出來寫成一個初始化函數。