poj并查集小結

并查集小結
并查集大體分為三個：普通的并查集，帶種類的并查集，擴充的并查集（主要是必須指定合并時的父子關系，或者統計一些資料，比如此集合内的元素數目。）


POJ-1182

經典的種類并查集

POJ-1308

用并查集來判斷一棵樹。。注意空樹也是樹，死人也是人。

POJ-1611

裸地水并查集

POJ-1703

種類并查集

POJ-1988

看上去似乎和種類并查集無關，但其實仔細想想，就是種類并查集。。。
隻不過是種類數目無窮大，通過合并，可以确定兩個物品之間的種類差（即高度差）

POJ-2236

裸地并查集，小加一點計算幾何

POJ-2492

裸地種類并查集

POJ-2524

又是裸地并查集

POJ-1456

正常思想是貪心+堆優化，用并查集确實很奇妙。。。下面的文章中有詳細介紹。

POJ-1733

種類并查集，先要離散化一下，不影響結果。。。

HDU-3038

上一道題的擴充，也是種類并查集，種類無窮大。。。。

POJ-1417

種類并查集，然後需要背包原理來判斷是否能唯一确定“好人”那一堆

POJ-2912

baidu的題，AC了，不過有點亂，有時間【【【再看看】】】

ZOJ-3261   NUAA-1087

逆向使用并查集就可以了。。。

POJ-1861  POJ-2560

Kruskal并查集

另外這個文章很好：
轉自：http://hi.baidu.com/czyuan%5Facm/blog/item/531c07afdc7d6fc57cd92ab1.html

      繼續資料結構的複習，本次的專題是：并查集。

      并查集，顧名思義，幹的就是“并”和“查”兩件事。很多與集合相關的操作都可以用并查集高效的解決。

       兩個操作代碼：
       int Find(int x)
       {
          if (tree[x].parent != x)
          {
              tree[x].parent = Find(tree[x].parent);
          }
          return tree[x].parent;
       }

       void Merge(int a, int b, int p, int q, int d)
       {
          if (tree[q].depth > tree[p].depth) tree[p].parent = q;
          else
          {
              tree[q].parent = p;
              if (tree[p].depth == tree[q].depth) tree[p].depth++;
          }
       }
       其中Find()函數用了路徑壓縮優化，而Merge()函數用了啟發式合并的優化(個人感覺有了路徑壓縮，啟發式合并優化的效果并不明顯，而經常因為題目和代碼的限制，啟發式合并會被我們省略)。

       提到并查集就不得不提并查集最經典的例子：食物鍊。
       POJ 1182 食物鍊
       http://acm.pku.edu.cn/JudgeOnline/problem?id=1182
       題目告訴有3種動物，互相吃與被吃，現在告訴你m句話，其中有真有假，叫你判斷假的個數(如果前面沒有與目前話沖突的，即認為其為真話)
這題有幾種做法，我以前的做法是每個集合(或者稱為子樹，說集合的編号相當于子樹的根結點，一個概念)中的元素都各自分為A, B, C三類，在合并時更改根結點的種類，其他點相應更改偏移量。但這種方法公式很難推，特别是偏移量很容易計算錯誤。
下面來介紹一種通用且易于了解的方法：
首先，集合裡的每個點我們都記錄它與它這個集合(或者稱為子樹)的根結點的相對關系relation。0表示它與根結點為同類，1表示它吃根結點，2表示它被根結點吃。
那麼判斷兩個點a, b的關系，我們令p = Find(a), q = Find(b)，即p, q分别為a, b子樹的根結點。
       1. 如果p != q，說明a, b暫時沒有關系，那麼關于他們的判斷都是正确的，然後合并這兩個子樹。這裡是關鍵，如何合并兩個子樹使得合并後的新樹能保證正确呢？這裡我們規定隻能p合并到q(剛才說過了，啟發式合并的優化效果并不那麼明顯，如果我們用啟發式合并，就要推出兩個式子，而這個推式子是件比較累的活…是以一般我們都規定一個子樹合到另一個子樹)。那麼合并後，p的relation肯定要改變，那麼改成多少呢？這裡的方法就是找規律，列出部分可能的情況，就差不多能推出式子了。這裡式子為 : tree[p].relation = (tree[b].relation – tree[a].relation + 2 + d) % 3; 這裡的d為判斷語句中a, b的關系。還有個問題，我們是否需要周遊整個a子樹并更新每個結點的狀态呢？答案是不需要的，因為我們可以在Find()函數稍微修改，即結點x繼承它的父親(注意是前父親，因為路徑壓縮後父親就會改變)，即它會繼承到p結點的改變，是以我們不需要每個都周遊過去更新。
       2. 如果p = q，說明a, b之前已經有關系了。那麼我們就判斷語句是否是對的，同樣找規律推出式子。即if ( (tree[b].relation + d + 2) % 3 != tree[a].relation ), 那麼這句話就是錯誤的。
       3. 再對Find()函數進行些修改，即在路徑壓縮前紀錄前父親是誰，然後路徑壓縮後，更新該點的狀态(通過繼承前父親的狀态，這時候前父親的狀态是已經更新的)。
       核心的兩個函數為：
       int Find(int x)
       {
           int temp_p;
          if (tree[x].parent != x)
          {
              // 因為路徑壓縮，該結點的與根結點的關系要更新(因為前面合并時可能還沒來得及更新).
              temp_p = tree[x].parent;
              tree[x].parent = Find(tree[x].parent);
              // x與根結點的關系更新(因為根結點變了)，此時的temp_p為它原來子樹的根結點.
              tree[x].relation = (tree[x].relation + tree[temp_p].relation) % 3;
          }
          return tree[x].parent;
       }

       void Merge(int a, int b, int p, int q, int d)
       {
          // 公式是找規律推出來的.
          tree[p].parent = q; // 這裡的下标相同，都是tree[p].
          tree[p].relation = (tree[b].relation – tree[a].relation + 2 + d) % 3;
       }

       而這種紀錄與根結點關系的方法，适用于幾乎所有的并查集判斷關系(至少我現在沒遇到過不适用的情況…可能是自己做的還太少了…)，是以向大家強烈推薦～～

       搞定了食物鍊這題，基本POJ上大部分基礎并查集題目就可以順秒了，這裡僅列個題目編号: POJ 1308 1611 1703 1988 2236 2492 2524。

       下面來講解幾道稍微提高點的題目:
       POJ 1456 Supermarket
       http://acm.pku.edu.cn/JudgeOnline/problem?id=1456
       這道題貪心的思想很明顯，不過O(n^2)的複雜度明顯不行，我們可以用堆進行優化，這裡講下并查集的優化方法(很巧妙)。我們把連續的被占用的區間看成一個集合(子樹)，它的根結點為這個區間左邊第一個未被占用的區間。
先排序，然後每次判斷Find(b[i])是否大于0，大于0說明左邊還有未被占用的空間，則占用它，然後合并(b[i], Find(b[i]) – 1)即可。同樣這裡我們規定隻能左邊的子樹合并到右邊的子樹(想想為什麼～～)。

       POJ 1733 Parity game
       http://acm.pku.edu.cn/JudgeOnline/problem?id=1733
       這題同樣用類似食物鍊的思想。
首先我們先離散化，因為原來的區間太大了(10^9)，我們可以根據問題數目離散成(10^4)。我們要了解，這裡的離散化并不影響最終的結果，因為區間裡1的奇偶個數與區間的大小無關(這句話有點奇怪，可以忽略…)，然後每次輸入a, b，我們把b++，如果他倆在一個集合内，那麼區間[a, b]裡1的個數相當于b.relation ^ a.relation，判斷對錯即可。如果不在一個集合内，合并集合(這裡我們規定根結點小的子樹合并根結點大的，是以要根據不同情況推式子)，修改子樹的根結點的狀态，子樹的其他結點狀态通過Find()函數來更新。

       hdu 3038 How Many Answers Are Wrong
       http://acm.hdu.edu.cn/showproblem.php?pid=3038
       上面那題的加強版，不需要離散化，因為區間的和與區間的大小有關(和上面的那句話對比下，同樣可以忽略之…)，做法與上面那題差不多，隻是式子變了，自己推推就搞定了。但這題還有個條件，就是每個點的值在[0, 100]之間，那麼如果a, b不在一個子樹内，我們就合并，但在合并之前還要判斷合并後會不會使得區間的和不合法，如果會說明該合并是非法的，那麼就不合并，同樣認為該句話是錯誤的。

       POJ 1417 True Liars(難)
       http://acm.pku.edu.cn/JudgeOnline/problem?id=1417
       并查集 + DP(或搜尋)。
       題目中告訴兩種人，一種隻說真話，一種隻說假話。然後告訴m條語句，問是否能判斷哪些人是隻說真話的那類人。
       其實并查集部分跟食物鍊還是相似，而且種類變少了一種，更容易了。我們可以通過并查集把有關系的一些人合并到一個集合内(具體方法參見食物鍊講解)。
       現在的問題轉化為，有n個集合，每個集合都有a, b連個數字，現在要求n個集合中各跳出一個數(a或者b)，使得他們之和等于n1(說真話的人數)。而這個用dp可以很好的解決，用f[i][j]表示到第i個集合和為j個的情況數，我們還用過pre[i][j]記錄目前選的是a還是b，用于後面判斷狀态。方程為f[i][j] = f[i – 1][j – a] + f[i – 1][j – b], j >= a, j >= b。如果最後f[n][n1] == 1說明是唯一的情況，輸出該情況，否則輸出 “no”(多解算no)
       注意點 :
       1. 這題的m, n1, n2都有可能出現0，可以特殊處理，也可以一起處理。
       2. 按上面的dp寫法，f[i][j]可能會很大，因為n可以達到三位數。其實我們關心的隻是f[i][j] 等于0，等于1，大于1三種情況，是以當f[i][j] > 1時，我們都讓它等于2即可。

       POJ 2912 Rochambeau(難)
       http://acm.pku.edu.cn/JudgeOnline/problem?id=2912
       Baidu Star 2006 Preliminary的題目，感覺出的很好，在并查集題目中算是較難的了。其實這題跟食物鍊完全一個磨子，同樣三類食物，同樣的互相制約關系。是以食物鍊代碼拿過來改都不需要改。但這題有個judge，他可以出任意手勢。于是我們的做法是，枚舉每個小孩為judge，判斷他為judge時在第幾句話出錯err[i](即到第幾句話能判斷該小孩不是judge)。
       1. 如果隻有1個小孩是judge時全部語句都是正确的，說明該小孩是judge，那麼判斷的句子數即為其他小孩的err[i]的最大值。如果
       2. 如果每個小孩的都不是judge(即都可以找到出錯的語句)，那麼就是impossible。
       3. 多于1個小孩是judge時沒有找到出錯的語句，就是Can not determine。     ZOJ 3261 Connections in Galaxy War
        http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3563
        nuaa 1087 聯通or不連通
        http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1087
        兩題做法差不多，都是反過來的并查集題目，先對邊集排序，然後把要删去的邊從二分在邊集中标記。然後并查集連接配接沒有标記的邊集，再按查詢反向做就可。第一題合并結點時按照題目要求的優先級合并即可。
　   
       這裡介紹的并查集題目，主要都是處理些集合之間的關系(這是并查集的看家本領～～)，至于并查集還有個用處就在求最小生成樹的Kruskal算法中，那個是圖論中求最小生成樹的問題(一般這個難點不在于并查集，它隻是用于求最小生成樹的一種方法)，就不在這裡贅述了～～

czyuan原創，轉載請注明出處。

種類并查集報告
POJ-1703    POJ-1182    POJ-2492都是這種題。

别人的報告，講得很好
原始位址：http://www.cppblog.com/tortoisewu/archive/2009/07/14/85501.html
——————————————————————————
poj 1182 解題報告
本來要先寫搜尋和DP的報告的，因為前面做的都是搜尋和DP，正好昨天做了這道并查集的題目，是以就順手寫下。這道題也讓我了解了好長時間，還是很有意義的，網上也沒有很詳細的解題報告。
題目：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1182

因為我是按網上通用分類做的，是以做之前就知道用并查集做，不過這道題是并查集的深入應用，沒有其它的那麼直覺。這裡我采用的是和網上主流方法一樣的方法，這裡先貼出源碼再深入解釋下。

#include <iostream>
using namespace std;
struct point{
    int parent;
    int kind;
} ufind[50010];
void init(int n);
int find(int index);
void unions(int rootx, int rooty, int x, int y, int dkind);
int main()
{
    int n,k,count=0,d,x,y;
    scanf(“%d%d”,&n,&k);
    
        init(n);
        while(k–)
        {
            scanf(“%d%d%d”,&d,&x,&y);
            if(x>n || y>n)
                count++;
            else if(d==2 && x==y)
                    count++;
            else
            {
                int rx=find(x);
                int ry=find(y);
                if(rx!=ry)
                    unions(rx,ry,x,y,d-1);
                else
                {
                    if(d==1 && ufind[x].kind!=ufind[y].kind)
                        count++;
                    if(d==2 && (ufind[x].kind-ufind[y].kind+3)%3!=1)
                        count++;
                }
            }
        }
        printf(“%d\n”,count);
    
    
    return 0;
}
void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        ufind[i].parent=i;
        ufind[i].kind=0;
    }
}
int find(int index)
{
    int temp;
    if(index==ufind[index].parent)
        return index;
    temp=ufind[index].parent;
    ufind[index].parent=find(ufind[index].parent);
    ufind[index].kind=(ufind[temp].kind+ufind[index].kind)%3;
    return ufind[index].parent;
}
void unions(int rootx, int rooty, int x, int y, int dkind)
{
    ufind[rooty].parent=rootx;
    ufind[rooty].kind=(-dkind+(ufind[x].kind-ufind[y].kind)+3)%3;
}

1.這裡并查集(ufind)的一個同類集合存放的是根據已有正确推斷有關聯的點，這裡的關聯包括了吃，被吃，同類三個關系；
2.關系是通過kind來表示的，其值為0，1，2，如果ufind[1].kind==ufind[2].kind，說明1，2點同類；如果
(ufind[1].kind-ufind[2].kind+3)%3==1，說明1吃2；
3.并查集是按索引部分組織起來的，即同一類的點都有共同的根結點；
4.并查集包括初始化(init)，查找(find)，合并(unions)操作，其中有很多關鍵點，我都在代碼中用紅色标記。下面逐一解釋這些關鍵點：
(1)ufind[i].kind=0;種類初始化為0，這個看似很簡單，但它其實保證了并查集中每一個類的根結點的kind屬性為0，這是後面兩個關鍵式推導的基礎；
(2)ufind[rooty].kind=(-dkind+(ufind[x].kind-ufind[y].kind)+3)%3;這句出現在合并操作裡面，這裡要解釋的是，在合并之前每個類的集合中所有父節點為根結點的點以及根結點，它們之間的關系都是正确的，合并之後隻保證了合并前原兩個集合的根結點之間的關系正确，即在新的合并後的集合中仍保證所有父節點為根結點的點以及根結點之間的關系正确。這樣我們在做合并操作時，是通過三個關系推到出預合并的兩個根結點(rootx,rooty)之間的正确關系的：x和rootx的關系，y和rooty的系，x和y的關系。這就是這個式子的由來，其中用到了前面說過的rootx和rooty為0的結論。
(3)ufind[index].kind=(ufind[temp].kind+ufind[index].kind)%3;這句出現在查找操作裡，作用是将待查找的點到它的根結點所經過的所有點進行兩個操作，一是把它們的父節點都設為根結點；二是按照從離根結點最近的那個點開始到待查找的點的順序把它們與根結點的關系設定成正确值(原先有可能是錯誤的，因為合并操作隻保證了所有父節點為根結點的點以及根結點之間的關系正确)。這樣之後這個集合中仍然保證了所有父節點為根結點的點以及根結點之間的關系正确，并且待考察的點的父節點為根結點。下面來解釋下為什麼要按照從離根結點最近的那個點開始到待查找的點的順序，這也是這個式子為什麼這麼寫的原因：假設1為根結點，Kind為0，其子節點為2，kind為k2，2的子節點為3，kind為k3；因為每次合并隻合并根結點，是以3在1，2合并前的根結點一定是2，即若2的kind為0，則3和2的關系就正确了，但合并時2的kind加上了k2，保證了1與2的關系正确而并沒有更新k3(這是因為并查集集合中無法從父節點找到子結點，是以等到查找時，要用到該點時再更新也不遲)，是以此時隻要将(k2+k3)%3就可以得到正确的以1為基準的3的kind。接下來，k3的kind修正了，k4可以以k3為基礎一樣通過此方法修正，直到要查的結點，并把它們全部挂到根結點上。
解釋就到這裡，我想了解時隻要畫個圖就能容易了解些，即以index和kind為結點做出集合的樹狀圖。這裡恰巧是3個關系，若是4個關系我想就要更新并查集機關集合的組織形式了，即要可以從根結點周遊全集和。