問題描述：

動態(tài)連通性：輸入為一列整數(shù)對胧奔，其中每個(gè)整數(shù)對都表示一個(gè)某種弄類型的對象矛市，一堆整數(shù)p q可以被理解為“p和q是相連的”焦影。當(dāng)程序從輸入中讀取了整數(shù)對p q時(shí)宣增，如果一直的所有整數(shù)對都不能說明p和q是相連的玫膀，那么則將這一對整數(shù)寫入到輸出中。

• p和q稱為觸點(diǎn)爹脾。
• p和q的通道稱為分量帖旨。

quick-find源碼：

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class UF {
    private int[] id;// 分量id(以觸點(diǎn)作為索引)
    private int count;// 分量數(shù)量

    public UF(int N) {
        count = N;
        id = new int[N];
        // 初始化分量id
        for (int i = 0; i < N; i++) {
            id[i] = i;
        }
    }

    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) return;
        for (int i = 0; i < id.length; i++) {
            if (id[i] == pID) id[i] = qID;
        }
        count--;
    }

    public static void main(String[] args) {
        int N = StdIn.readInt();
        UF uf = new UF(N);
        while(!StdIn.isEmpty()) {
            int p = StdIn.readInt();
            int q = StdIn.readInt();
            if (uf.connected(p, q)) continue;
            uf.union(p, q);
            StdOut.println(p + " " + q);
        }
        StdOut.println(uf.count + " components");
    }

}

程序輸入取自tinyUF.text文件

10
4 3
3 8
6 5
9 4
2 1
8 9
5 0
7 2
6 1
1 0
6 7

程序入口

public static void main(String[] args) {
    int N = StdIn.readInt();// 讀取觸點(diǎn)數(shù)量
    UF uf = new UF(N);// 初始化N個(gè)分量
    while(!StdIn.isEmpty()) {
        int p = StdIn.readInt();
        int q = StdIn.readInt();// 讀取整數(shù)對
        if (uf.connected(p, q)) continue;// 如果已經(jīng)連通則忽略
        uf.union(p, q);// 歸并分量
        StdOut.println(p + " " + q);// 打印鏈接
    }
    StdOut.println(uf.count + " components");
}

算法邏輯分析

public int find(int p) {
    return id[p];
}

public void union(int p, int q) {
    // 將p和q歸并到相同的分量中
    int pID = find(p);
    int qID = find(q);
    if (pID == qID) return;// 如果p和q已經(jīng)在相同的分量之中則不需要采取任何行動
    // 將p的分量重命名為q的名字
    for (int i = 0; i < id.length; i++) {
        if (id[i] == pID) id[i] = qID;
    }
    count--;
}

算法復(fù)雜度分析

• union()操作訪問數(shù)組的次數(shù)在(N+3)到(2N+1)之間。N為id.length灵妨。
  1. 當(dāng)整數(shù)對只有一個(gè)時(shí),訪問次數(shù)為2+(N+1)
  2. 當(dāng)整數(shù)對的數(shù)量為N時(shí)解阅，訪問次數(shù)為2+N+(N-1)
• 假設(shè)我們使用quick-find算法來解決動態(tài)連通性問題并且最后只得到了一個(gè)連通分量，那么這至少需要調(diào)用N-1次union()泌霍。
• 即至少(N+3)(N-1) ~ N2次數(shù)組訪問————我們馬上可以猜想動態(tài)連通性的quick-find算法是平方級別的货抄。