飯後小甜點leetcode——并查集

文章目錄

• • 并查集
  • • 概述
    • 實作
    • 相關題目總結
    • • 求集合個數。
      • 求備援邊

并查集

概述

并查集是一種用在圖論中的資料結構，最主要的功能就是：

1. 檢視兩點是否相連。O(1)複雜度。就是看一下這兩個節點的祖宗節點是不是同一個。
2. 合并兩個點所在集合。O(logn)複雜度。就是讓一個集合的祖宗節點成為另一個集合祖宗節點的父親節點

實作

• 需要一個parent數組，記錄每個節點的父親節點
• 可以加上路徑壓縮，也就是在find祖宗的時候順路把祖宗變父親節點，這樣可以讓樹的層數減少，加快查詢速度
• rank是對集合的一種衡量名額，rank高的集合節點層數多，合并的時候把層數少的合并到層數多的，那麼新集合的層數不變

public class UnionFind
{
    private int[] parent;
    private int[] rank;

    public UnionFind(int size)
    {
        parent = new int[size];
        rank = new int[size];
        for (var i = 0; i < size; i++)
        {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int GetSize()
    {
        return parent.Length;
    }

    /// <summary>
    /// 查找元素p所對應的集合編号
    /// </summary>
    private int Find(int p)
    {
        if (p < 0 && p >= parent.Length)
        {
            throw new ArgumentException("p is out of bound.");
        }

        while (p != parent[p])
        {
            parent[p] = parent[parent[p]];
            p = parent[p];
            //不用更新rank，因為rank低的依舊低，隻是用來表示一個大概的排名作為union的參考
        }

        return p;
    }

    /// <summary>
    /// 檢視元素p, q是否屬于一個集合
    /// </summary>
    public bool IsConnected(int p, int q)
    {
        return Find(p) == Find(q);
    }

    /// <summary>
    /// 合并p，q所在集合
    /// </summary>
    public void UnionElements(int p, int q)
    {
        var pRoot = Find(p);
        var qRoot = Find(q);
        if (pRoot == qRoot)
        {
            return;
        }

        if (rank[pRoot] < rank[qRoot])
        {
            parent[pRoot] = qRoot;
        }
        else
        {
            parent[qRoot] = pRoot;
            if (rank[pRoot] == rank[qRoot])
            {
                rank[pRoot]++;
            }
        }
    }
}

           

相關題目總結

求集合個數。

也就是求連通圖個數，在uf中keep一個count變量，每union一對兒節點，count–，這個count就是最後的連通圖個數。

【易錯點】我一直以為加了路徑壓縮的話，到了最後parent數組中數的種類數就是集合個數，但事實上，不是每一個節點都在最後被壓縮了路徑，有的節點它一開始的祖宗節點，通過該節點兄弟可能歸入到了别的祖宗節點門下，壓縮的路徑并沒有經過這個節點，是以這個節點在parent數組依舊保留着一開始的祖宗節點，是以不能這麼算集合個數。

【leetcode中相關題目】

• 547. 朋友圈
• 200. 島嶼數量
• 323. 無向圖中連通分量的數目

求備援邊

給Union函數加一個傳回值，如果兩個節點本身就是同祖宗那麼union失敗，傳回false，其他情況傳回true，然後對于graph的每個邊，依次union，如果碰到union失敗的情況，則說明目前邊是備援的。

【leetcode中相關題目】

• 684. 備援連接配接