文章目錄

1. 并查集概念
2. 并查集的3種實作
- 2.1 quick-find實作
- 2.2 quick-union實作
- 2.3 權重quick-union
- 2.4 路徑壓縮

1. 并查集概念

問題的輸入是一列整數對，其中每個整數都表示一個某種類型的對象，一對整數 p，q 可以被了解為“p 和 q 是相連的”。我們假設“相連”是一種等價關系，這也就意味着它具有以下3個性質：

自反性：p和p是相連的
對稱性：p與q相連則q與p也相連
傳遞性：p與q相連，q與r相連，則p與r也相連

并查集的三種實作方式及相關問題1. 并查集概念2. 并查集的3種實作

作用：

并查集可以進行集合合并的操作（并）
并查集可以查找元素在哪個集合中（查）
并查集維護的是一堆集合（集）

主要API:

UF(int N)

:以整數辨別（0 到 N-1）初始化 N 個觸點

void union(int p, int q)

: 在 p 和 q 之間添加一條連接配接

int find(int p)

: p（0 到 N-1）所在的分量的辨別符

boolean connected(int p, int q)

: 如果 p 和 q 存在于同一個分量中則傳回 true

int count()

: 連通分量的數量

2. 并查集的3種實作

2.1 quick-find實作

查找得快

對于節點p和節點q

當id[p]==id[q]時說明p,q屬于同一個連通分量，二者連通
在同一個連通分量中id值完全相同
判斷connected(p,q)時隻需要指定id[p]是否等于id[q]即可
connected(p,q) 如果p,q不連通，那麼将所有和id[p]相同的連通分量号全部變為id[q](反之亦可) 這樣就保證p,q在一個連通分量中了

并查集的三種實作方式及相關問題1. 并查集概念2. 并查集的3種實作

import java.util.Scanner;
public class UnionFind {
    private int[] id;
    private int count;
    public UnionFind(int N)
    {
        count=N;
        id=new int[N];
        for(int i=0;i<N;i++)
        {
            id[i]=i;//初始時相當于0-N-1個連通分量 編号為0-N-1
        }
    }
    public int count()
    {
        return count;
    }
    public boolean connected(int p,int q)
    {
        return find(p)==find(q);
    }
    public int find(int p)
    {
        return id[p];//傳回連通分号
    }
    public void union(int p,int q)
    {
        int pID=find(p);
        int qID=find(q);
        if(pID==qID)//p q如果已經在同一個連通分量中則不需要合并
            return;
        for(int i=0;i<id.length;i++)//将和p屬于同一個連通分量的元素的連通編号改成和q連通分号一緻
        {
            if(id[i]==pID)
                id[i]=qID;
        }
        count--;//連通分量減一
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        UnionFind uf=new UnionFind(N);
        while(sc.hasNext())
        {
            int p=sc.nextInt();
            int q=sc.nextInt();
            if(uf.connected(p, q))//p q如果已經連通則不列印連接配接
                continue;
            uf.union(p, q);
            System.out.println(p+"---"+q);
        }
        System.out.println(uf.count()+" components");
    }
    
}

在 quick-find 算法中，每次 find() 調用隻需要通路數組一次，而歸并兩個分量的union() 操作通路數組的次數在 (N+3) 到 (2N+1) 之間。

優勢：查找快

不足：合并較慢

2.2 quick-union實作

合并得快

quick-union和quick-find的比較：

quick-union加快了union的速度，時間複雜度是O(1), 但是find的速度低了，是O(n)
quick-find加快了find的速度，時間複雜度是O(1), 但是union的速度降低了，是O(n)

思想：

在實作 find() 方法時，我們從給定的觸點開始，由它的連結得到另一個觸點，再由這個觸點的連結到達第三個觸點，如此繼續跟随着連結直到到達一個根觸點，即連結指向自己的觸點（你将會看到，這樣一個觸點必然存在）。當且僅當分别由兩個觸點開始的這個過程到達了同一個根觸點時它們存在于同一個連通分量之中

并查集的三種實作方式及相關問題1. 并查集概念2. 并查集的3種實作

可以了解成最上面一行是數組的下标0-9，下面一行是數值的元素值，當數組下标和對應的元素不相等時，就将數組元素作為下标達到下一個數組元素, 以find[5]為例：

id[5]==0!=5 下一步 id[0]
id[0]==1!=0 下一步 id[1]
id[1]==1 結束

為了保證這個過程的有效性，我們需要union(p, q) 來保證這一點。它的實作很簡單：我們由 p 和 q 的連結分别找到它們的根觸點，然後隻需将一個根觸點連結到另一個即可将一個分量重命名為另一個分量，是以這個算法叫做 quick-union。

import java.util.Scanner;
public class UnionFind {
    private int[] id;
    private int count;
    public UnionFind(int N)
    {
        count=N;
        id=new int[N];
        for(int i=0;i<N;i++)
        {
            id[i]=i;//初始時相當于0-N-1個連通分量 編号為0-N-1
        }
    }
    public int count()
    {
        return count;
    }
    public boolean connected(int p,int q)
    {
        return find(p)==find(q);
    }
    public int find(int p)
    {
        while(p!=id[p])
            p=id[p];//尋找p所在的根節點
        return p;
    }
    public void union(int p,int q)
    {
        int pROOT=find(p);
        int qROOT=find(q);
        if(pROOT==qROOT)//p q如果已經在同一個連通分量中則不需要合并
            return;
        id[pROOT]=qROOT;//p所在分量的根節點連接配接到q所在分量的根節點上
        count--;//連通分量減一
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        UnionFind uf=new UnionFind(N);
        while(sc.hasNext())
        {
            int p=sc.nextInt();
            int q=sc.nextInt();
            if(uf.connected(p, q))
                continue;
            uf.union(p, q);
            System.out.println(p+"---"+q);
        }
        System.out.println(uf.count()+" components");
    }
    
}

quick-union 算法中的 find() 方法通路數組的次數為 1 加上給定觸點所對應的節點的深度的兩倍。union() 和 connected() 通路數組的次數為兩次 find() 操作（如果 union() 中給定的兩個觸點分别存在于不同的樹中則還需要加 1）。

2.3 權重quick-union

上面的quick-union存在以下問題：

并查集的三種實作方式及相關問題1. 并查集概念2. 并查集的3種實作

由于在union中是随意将一棵樹連接配接到另外一棵樹上，是以會出現樹的深度過高的問題，在權重quick-union中可以保證小樹連接配接到大的樹上：

并查集的三種實作方式及相關問題1. 并查集概念2. 并查集的3種實作

import java.util.Scanner;
public class UnionFind {
    private int[] id;//每個位置對應的連通号
    private int[] sz;//每個連通量（樹）的節點數目
    private int count;
    public UnionFind(int N)
    {
        count=N;
        id=new int[N];
        for(int i=0;i<N;i++)
        {
            id[i]=i;//初始時相當于0-N-1個連通分量 編号為0-N-1
        }
        sz=new int[N];
        for(int i=0;i<N;i++)
            sz[i]=1; //初始時，每個連通分量隻有1個節點，節點數目是1
    }
    public int count()
    {
        return count;
    }
    public boolean connected(int p,int q)
    {
        return find(p)==find(q);
    }
    public int find(int p)
    {
        while(p!=id[p])
            p=id[p];
        return p;
    }
    public void union(int p,int q)
    {
        int pROOT=find(p);
        int qROOT=find(q);
        if(pROOT==qROOT)//p q如果已經在同一個連通分量中則不需要合并
            return;
        if(sz[pROOT]<sz[qROOT])//p所在的樹小
        {
            id[pROOT]=qROOT;//p所在樹的根節點連接配接到q所在樹的根節點上
            sz[qROOT]+=sz[pROOT];
        }
        else 
        {
            id[qROOT]=pROOT;
            sz[pROOT]+=sz[qROOT];
        }
       
        count--;//連通分量減一
    }
    public static void main(String[] args) {
        
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        UnionFind uf=new UnionFind(N);
        while(sc.hasNext())
        {
            int p=sc.nextInt();
            int q=sc.nextInt();
            if(uf.connected(p, q))
                continue;
            uf.union(p, q);
            System.out.println(p+"---"+q);
        }
        System.out.println(uf.count()+" components");
    }
    
}

并查集的三種實作方式及相關問題1. 并查集概念2. 并查集的3種實作

2.4 路徑壓縮

這裡是對find算法的一種優化：

原始的find:

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

優化後的find:

//調用find函數每次向樹根周遊的同時，順手将樹高縮短了，最終所有樹高都不會超過 3
	public int find(int p)
    {
        while(p!=parent[p])
        {
            parent[p]=parent[parent[p]];//添加部分
            p=parent[p];
        }
        return p;
    }

即周遊到某個節點X時，假設此時X的父節點是Y，Y的父節點是Z，直接将X連接配接到Z上，Z成為X的父節點

并查集的三種實作方式及相關問題1. 并查集概念2. 并查集的3種實作

文章目錄

1. 并查集概念

2. 并查集的3種實作

2.1 quick-find實作

2.2 quick-union實作

2.3 權重quick-union

2.4 路徑壓縮

繼續閱讀

資料結構與算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

hdu7108哈希