并查集

集合的表示

　　集合運算：交、并、補、差，判定一個元素是否屬于某一集合

　　并查集：集合并、查某元素屬于什麼集合

　　并查集問題中集合存儲如何實作：

①可以用樹結構表示集合，樹的每個結點代表一個集合元素

②采用數組存儲形式

合并後根為負數，負數代表根，其絕對值代表個數（優化）。

1.查找某個元素所在的集合（用根結點表示）

2.集合的并運算

　　①分别找到X1和X2兩個元素所在集合樹的根結點

　　②如果它們不同根，則将其中一個根結點的父結點指針設定成另一個根結點的數組下标。

為了改善合并以後的查找性能，采用小的集合合并到相對大的集合中。

#define MAXN 1000                  /* 集合最大元素個數 */
typedef int ElementType;           /* 預設元素可以用非負整數表示 */
typedef int SetName;               /* 預設用根結點的下标作為集合名稱 */
typedef ElementType SetType[MAXN]; /* 假設集合元素下标從0開始 */
 
void Union( SetType S, SetName Root1, SetName Root2 )
{ /* 這裡預設Root1和Root2是不同集合的根結點 */
    /* 保證小集合并入大集合 */
    if ( S[Root2] < S[Root1] ) { /* 如果集合2比較大 */  //大小集合按照元素個數比較的
        S[Root2] += S[Root1];     /* 集合1并入集合2  */
        S[Root1] = Root2;
    }
    else {                         /* 如果集合1比較大 */
        S[Root1] += S[Root2];     /* 集合2并入集合1  */
        S[Root2] = Root1;
    }
}
 
SetName Find( SetType S, ElementType X )
{ /* 預設集合元素全部初始化為-1 */
    if ( S[X] < 0 ) /* 找到集合的根 */
        return X;
    else
        return S[X] = Find( S, S[X] ); /* 路徑壓縮 */
}      

C/C++基本文法學習

STL

C++ primer