并查集算法分析

并查集算法

一、并查集能解決哪類問題

1. 前提條件
   • 如果A與B有關系，B與C也有關系，那麼，A與C就有關系；
   • 舉例：在下圖中，A與B是連通的，B與C也是連通的，那麼顯然，A與C就是連通的。我們把A,B,C稱之為節點。
2. 問題描述
   • 在下列群節點中，已知一些節點之間的關系情況現在給出任意兩個節點x和y，判斷x和y是否有關系？這些節點中共有多少個獨立的群體？

二、怎樣解決

1. 解決思路
   • 每個群體推選出一個根節點；
   • 兩個節點是否在一個群體中，隻需要判斷它們的根節點是否相同；
   • 有多少個根節點就有多少個群體。
2. 實作方法（C/C++語言實作）
   • 初始化

     const int max=10000;//max為定義的最大節數
     int pre[max];//max為定義的最大節數
     void init(){//初始化，每個節點都是根節點
     	for(int i=0;i<max;i++)
     		pre[i]=i;
     }
                

   • 尋找根節點

     int find(int node){
     	while(pre[node]!=node)
     		node=pre[node];
     	return node;
     }
                

   • 并為一個集合

     void join(int node1,int node2){
     	node1=find(node1);
         node2=find(node2);
         if(node1!=node2)//判斷兩個節點x,y是否有聯系
             pre[node1]=node2;
     }
                

三、例題

• L 2 − 010 L2-010 L2−010排座位
• L 2 − 024 L2-024 L2−024部落
• L 2 − 007 L2-007 L2−007家庭房