第十一章 圖論part05

并查集理論基礎(chǔ)

并查集理論基礎(chǔ)很重要，明確并查集解決什么問(wèn)題，代碼如何寫，對(duì)后面做并查集類題目很有幫助。
文章講解

并查集的 Java 代碼模板

import java.util.Arrays;

public class UnionFind {
    private int[] parent;  // 存儲(chǔ)每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)
    private int n;  // 節(jié)點(diǎn)數(shù)量

    // 構(gòu)造函數(shù)，初始化并查集
    public UnionFind(int n) {
        this.n = n;
        parent = new int[n];
        init();
    }

    // 并查集初始化
    private void init() {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    // 尋找根節(jié)點(diǎn)，帶路徑壓縮
    public int find(int u) {
        if (u == parent[u]) {
            return u;
        } else {
            parent[u] = find(parent[u]);
            return parent[u];
        }
    }

    // 判斷兩個(gè)節(jié)點(diǎn)是否在同一個(gè)集合
    public boolean isSame(int u, int v) {
        return find(u) == find(v);
    }

    // 將兩個(gè)節(jié)點(diǎn)加入到同一個(gè)集合
    public void join(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            parent[rootV] = rootU;
        }
    }

    // 測(cè)試用例
    public static void main(String[] args) {
        int n = 1005;  // 根據(jù)具體問(wèn)題確定節(jié)點(diǎn)數(shù)量
        UnionFind uf = new UnionFind(n);

        // 示例操作
        uf.join(1, 2);
        uf.join(3, 4);
        System.out.println(uf.isSame(1, 2));  // true
        System.out.println(uf.isSame(1, 3));  // false
        uf.join(2, 3);
        System.out.println(uf.isSame(1, 3));  // true
    }
}

代碼解釋：

1. 初始化 (init)：將每個(gè)節(jié)點(diǎn)初始化為自身的父節(jié)點(diǎn)，表示每個(gè)節(jié)點(diǎn)開(kāi)始時(shí)都是獨(dú)立的集合。
2. 尋找根節(jié)點(diǎn) (find)：使用路徑壓縮技術(shù)來(lái)加速后續(xù)查詢。在查找過(guò)程中，將訪問(wèn)過(guò)的節(jié)點(diǎn)直接鏈接到根節(jié)點(diǎn)。
3. 判斷是否在同一集合 (isSame)：通過(guò)比較兩個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)來(lái)判斷它們是否在同一個(gè)集合中。
4. 將兩個(gè)節(jié)點(diǎn)加入同一集合 (join)：將一個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)鏈接到另一個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)，從而將兩個(gè)集合合并。

按秩（rank）合并
二刷再看

尋找存在的路徑

并查集裸題，學(xué)會(huì)理論基礎(chǔ)后，本題直接可以直接刷過(guò)
文章講解

import java.util.Scanner;

public class Main {

    static private int[] father; // 按照節(jié)點(diǎn)大小定義數(shù)組大小

    // 并查集初始化
    static public void init(int n) {
        father = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            father[i] = i;
        }
    }

    // 并查集里尋根的過(guò)程
    static public int find(int u) {
        if (u == father[u]) {
            return u;
        } else {
            father[u] = find(father[u]); // 路徑壓縮
            return father[u];
        }
    }

    // 判斷 u 和 v 是否找到同一個(gè)根
    static public boolean isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }

    // 將 v -> u 這條邊加入并查集
    static public void join(int u, int v) {
        u = find(u); // 尋找 u 的根
        v = find(v); // 尋找 v 的根
        if (u == v) return; // 如果發(fā)現(xiàn)根相同，則說(shuō)明在一個(gè)集合，不用兩個(gè)節(jié)點(diǎn)相連直接返回
        father[v] = u;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        init(n);// 初始化并查集

        // 處理每一條邊，將其加入并查集
        while (m-- > 0) {
            int s = sc.nextInt();
            int t = sc.nextInt();
            join(s, t);
        }

        // 讀取源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)
        int source = sc.nextInt();
        int destination = sc.nextInt();

        // 判斷源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)是否屬于同一集合
        if (isSame(source, destination)) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }

    }
}