并查集

入門

并查集（union-find set）是一種不算太“低級”的數(shù)據(jù)結構，在算法競賽中比較常見。簡而言之，它專門用來高效地處理不相交集合（disjoint sets）的合并及查詢問題。

Bernard A. Galler和Michael J. Fischer于1964年提出了并查集的森林表示形式：用一棵（多叉）樹來表示一個集合，樹中的每個節(jié)點都保存著對它的父節(jié)點的引用，所有的不相交集合即可形成一個森林，并且每個集合的“代表”就是對應的樹的根節(jié)點。

根據(jù)上述表示形式，我們就可以定義并查集的三種基本操作。下面用偽碼表示之。

• 從單節(jié)點x創(chuàng)建集合
  每個集合剛開始都只有一個元素，通過后面的合并操作再形成多元素的集合。

function make(x) {
  x.parent = x;
}

• 查詢x位于哪個集合
  注意返回的是x所在集合的根節(jié)點，前面說過，根節(jié)點可以作為集合的“代表”。

function find(x) {
  if (x.parent == x) {
    return x;
  } else {
    return find(x.parent);
  }
}

當然也可以寫成迭代形式。

function find(x) {
  while (x.parent != x) {
    x = x.parent;
  }
  return x;
}

• 合并x、y所在的兩個集合
  就是分別找到它們所處集合的根節(jié)點，并將兩個集合的根連接在一起。

function union(x, y) {
  rootx = find(x);
  rooty = find(y);
  if (rootx == rooty) {
    return;
  }
  rootx.parent = rooty;
}

上面的寫法是最樸素的邏輯，雖然簡單，但性能有風險——因為集合形成的樹有可能會非常不平衡，甚至成為單枝樹（退化成線性的）。所以在實際應用時會采取兩方面優(yōu)化：一是路徑壓縮（path compression），二是按秩合并（union by rank）。

路徑壓縮

根據(jù)并查集結構的定義，樹的每個節(jié)點其實都可以直接連接到根節(jié)點，而樹表示的集合是不變的。那么我們在執(zhí)行查詢操作時，可以順便對查詢路徑中經(jīng)過的每個節(jié)點都遞歸地更改指向，讓它們連接到根節(jié)點上，使得樹盡量扁平化，之后再執(zhí)行查詢操作遍歷的節(jié)點就會變少，效率提高。最理想情況下，樹應該只有兩層，頂層只有根節(jié)點，第二層是所有葉子節(jié)點。

下面給出路徑壓縮思路下查詢操作的邏輯。

function find(x) {
  if (x.parent != x) {
    x.parent = find(x.parent);
  }
  return x.parent;
}

以及等價的迭代寫法，即先將父節(jié)點指向祖父節(jié)點，再將當前節(jié)點指向父節(jié)點。

function find(x) {
  while (x.parent != x) {
    x.parent = x.parent.parent;
    x = x.parent;
  }
  return x;
}

按秩合并

我們已經(jīng)知道，樹的深度會影響并查集算法的效率，那么在兩個集合合并時，可以人為地將深度較小的樹連接到深度較大的樹的根節(jié)點上。合并的結果樹的深度要么不會增加，要么只增加1（即當兩棵樹的深度相同時）。這里引入“秩”（rank）的概念：

• 單元素集合樹的秩為0；
• 當兩個秩同為r的集合樹做合并操作時，結果樹的秩為r + 1。

實際實現(xiàn)時，可以將秩存儲在根節(jié)點。為什么不直接沿用深度的概念呢？因為按秩合并幾乎都與路徑壓縮一同使用，路徑壓縮之后樹會變扁平，深度和秩就不是一回事了。

下面給出按秩合并思路下創(chuàng)建集合和合并操作的邏輯。

function make(x) {
  x.parent = x;
  x.rank = 0;
}

function union(x, y) {
  rootx = find(x);
  rooty = find(y);
  if (rootx == rooty) {
    return;
  }
  if (rootx.rank < rooty.rank) {
    rootx.parent = rooty;
  } else if (rootx.rank > rooty.rank) {
    rooty.parent = rootx;
  } else {
    rooty.parent = rootx;
    rootx.rank++;
  }
}

復雜度

如果同時使用上述兩種優(yōu)化，如果在有n個元素的并查集上進行m次查詢和合并操作，其時間復雜度為O(mα(n))，其中α(n)為阿克曼函數(shù)A(n, n)的反函數(shù)。證明過程非常硬核，詳見《算法導論》第21章第4節(jié)。

英文維基中《Proof of O(log*n) time complexity of union–find》一文也給出了平攤時間復雜度為O(mlog*n)的證明，相對容易明白一些。其中l(wèi)og*為迭代對數(shù)，即：

不管是反阿克曼函數(shù)還是迭代對數(shù)，它們的增長速度都極其緩慢，接近常數(shù)級別，這也從側面說明了并查集的高效性。

應用舉例

并查集常常用來解決網(wǎng)絡中的連通性問題。這里的網(wǎng)絡是廣義的，除了計算機網(wǎng)絡之外，還可以是社交體系里的人際關系網(wǎng)、生物學里的食物網(wǎng)等等。如果將網(wǎng)絡抽象為圖結構，那么并查集可以方便地確定兩點是否連通（是否在同一個集合內(nèi)），以及共有多少個連通分量（不相交集合數(shù)）。下面舉個簡單的例子。

LeetCode 547：Friend Circles

題目大意：一個班級有N（N≤200）位學生，給出一個N*N的矩陣M，M[i][j]=M[j][i]=1表示第i位和第j位學生是朋友關系。確定這些學生中有多少個“朋友圈”，“朋友圈”指的是一組有直接或間接朋友關系的人。

這就是上述“在人際關系網(wǎng)中確定連通分量數(shù)”的例子，朋友圈的數(shù)量其實就是并查集內(nèi)不相交集合的數(shù)量。它的數(shù)據(jù)規(guī)模比較小，就算是用樸素解法也可以AC，但是作為例題，我們還是老老實實寫一個完全版，代碼如下。

class Solution {
  final int MAXN = 201;
  int[] parent = new int[MAXN];
  int[] rank = new int[MAXN];

  void make(int x) {
    parent[x] = x;
    rank[x] = 0;
  }

  int find(int x) {
    while (parent[x] != x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }

  boolean union(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry) {
      if (rank[rx] <= rank[ry]) {
        parent[rx] = ry;
        rank[ry] = Math.max(rank[rx] + 1, rank[ry]);
      } else {
        parent[ry] = rx;
        rank[rx] = Math.max(rank[rx], rank[ry] + 1);
      }
      return true;
    }
    return false;
  }

  public int findCircleNum(int[][] M) {
    int n = M.length, result = n;
    for (int i = 0; i < n; i++) {
      make(i);
    }
    for (int i = 0; i < n; i++) {
      for (int j = i; j < n; j++) {
        if (M[i][j] == 1) {
          if (union(i, j)) {
            result--;
          }
        }
      }
    }
    return result;
  }
}

在實際應用中，并查集用簡單的數(shù)組就能表示：parent數(shù)組存儲某節(jié)點的父節(jié)點，rank數(shù)組存儲（根）節(jié)點的秩。另外，為了避免合并完之后再重新掃描統(tǒng)計一遍根節(jié)點的數(shù)量，可以在每一次成功的合并之后將總數(shù)減去1（初始的朋友圈數(shù)量自然是N）。

如果題目改成判斷兩個人x、y是否位于同一個朋友圈內(nèi)，使用條件find(x) == find(y)即可。

根據(jù)本節(jié)開頭對連通性問題的描述，這道題（以及其他不少可以用并查集解決的題目）用DFS解決也比較自然，解法就略去了。不過，并查集無法獲知兩點之間的路徑，而DFS可以，所以要根據(jù)實際情況靈活使用。

Kruskal算法與并查集

算法介紹

Kruskal算法是圖的兩種經(jīng)典最小生成樹（MST）算法之一（另外一個是Prim），在大學數(shù)據(jù)結構和圖論課程中肯定會講到。這里先簡介一下它的算法流程：

1. 新建圖G'，其中包含原圖G中相同的頂點，但沒有邊；
2. 將原圖G中所有的邊按照權值從小到大排序；
3. 從權值最小的邊開始，如果這條邊連接的兩個頂點在G'里不存在于同一個連通分量中（即這條邊是橋邊，添加它不會構成環(huán)），則將它添加到G'；
4. 重復上一步，直到G'中的所有頂點都位于同一個連通分量，即形成最小生成樹。

為了方便理解，下面的圖示出在一張圖上執(zhí)行Kruskal算法的流程。綠色邊是最小生成樹的邊，紅色邊是不滿足上述步驟3條件的邊。

由Kruskal算法的流程可見，關鍵點有二：一是需要判斷兩個點是否位于同一個連通分量，二是合并兩個連通分量（添加橋邊之后），這恰好是并查集所擅長的。

該算法的時間復雜度可以這樣考慮：第1步初始化為O(|V|)，第2步的排序為O(|E|log|E|)（很多排序算法都是這個復雜度），而第3步并查集操作的復雜度是O(|E|α(|V|))。由于這幾步是順序執(zhí)行的，整個算法的時間復雜度應該取上面三個的最大者，即O(|E|log|E|)。

下面還是舉個例題來說明。

應用舉例

LeetCode上好像沒幾個MST的題目，從當年整天刷的POJ挑一個簡單的吧。

POJ 1251：Jungle Roads

純粹的MST題目，輸入各個村莊之間道路的長度，求能夠將這些村莊全部連接起來的最小路徑總長。

根據(jù)題意，圖的頂點數(shù)小于27，邊數(shù)小于75，規(guī)模也很小，所以Kruskal+路徑壓縮并查集就可以水過去了。代碼如下。

const int MAXN = 101;
int n, m, cnt, w;
char u[4], v[4];
int parent[MAXN];

struct Edge {
  int u, v, w;
}e[MAXN];

bool comp(Edge a, Edge b) {
  return a.w < b.w;
}

int find(int x) {
  return x == parent[x] ? x : parent[x] = find(parent[x]);
}

void unite(int x, int y) {
  x = find(x);
  y = find(y);
  parent[x] = y;
}

int kruskal(int n) {
  int result = 0;
  for (int i = 0; i < n; i++) {
    if (find(e[i].u) != find(e[i].v)) {
      unite(e[i].u, e[i].v);
      result += e[i].w;
    }
  }
  return result;
}

int main() {
  while (scanf("%d", &n) && n) {
    cnt = 0;
    for (int i = 0; i < n; i++) {
      parent[i] = i;
    }
    for (int i = 0; i < n - 1; i++) {
      scanf("%s%d", u, &m);
      for (int j = 0; j < m; j++) {
        scanf("%s%d", v, &w);
        e[cnt++] = {u[0] - 'A', v[0] - 'A', w};
      }
    }
    sort(e, e + cnt, comp);
    printf("%d\n", kruskal(cnt));
  }
  return 0;
}

成功AC，民那晚安。