問題描述

有 n 個(gè)城市，其中一些彼此相連，另一些沒有相連。如果城市 a 與城市 b 直接相連，且城市 b 與城市 c 直接相連，那么城市 a 與城市 c 間接相連。

省份 是一組直接或間接相連的城市，組內(nèi)不含其他沒有相連的城市。

給你一個(gè) n x n 的矩陣 isConnected ，其中 isConnected[i][j] = 1 表示第 i 個(gè)城市和第 j 個(gè)城市直接相連，而 isConnected[i][j] = 0 表示二者不直接相連。

返回矩陣中 省份 的數(shù)量。

示例 1：

image

輸入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
輸出：2

示例 2：

image

輸入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
輸出：3

提示：

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] 為 1 或 0
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

并查集

主要步驟

初始化

準(zhǔn)備n個(gè)節(jié)點(diǎn)表示n個(gè)元素，在初始化時(shí)，彼此之間無關(guān)聯(lián)，即均單獨(dú)成樹

合并

合并即為合并兩個(gè)樹,由于每個(gè)樹表示一個(gè)集合(即相同類別，無順序之分)，故只需要讓一個(gè)樹的根節(jié)點(diǎn)指向另一個(gè)樹即可。合并的例子：

查詢

查詢即查詢兩個(gè)元素是否是同一集合中，即查詢對應(yīng)的兩個(gè)節(jié)點(diǎn)是否在同一個(gè)樹上，因此只需要查詢兩個(gè)節(jié)點(diǎn)所對應(yīng)的樹的根節(jié)點(diǎn)是否一致即可。

優(yōu)化

主要優(yōu)化思路為盡可能使樹的高度降低，從而盡可能減少查詢的時(shí)間復(fù)雜度

路徑壓縮

路徑壓縮

rank排序合并(使得樹的深度小)

rank排序

代碼實(shí)現(xiàn)

C++實(shí)現(xiàn)：

class Solution {
public:
    // 內(nèi)部維護(hù)一個(gè)父親節(jié)點(diǎn)的數(shù)組parent和節(jié)點(diǎn)深度的數(shù)組rank
    vector<int> parent;
    vector<int> rank;

    // 初始化并查集的數(shù)據(jù)，全部節(jié)點(diǎn)的深度為0，父節(jié)點(diǎn)為本身
    void init(int N)
    {
        parent = vector<int>(N);
        rank = vector<int>(N,0);
        for(int i = 0;i < N;++i) parent[i] = i;
    }
    
    // 使用遞歸的方式查找根節(jié)點(diǎn)
    int find(int x)
    {
        if(parent[x] == x) return x;
        //  //這一步很巧妙，既通過遞歸找到根節(jié)點(diǎn)，又同時(shí)完成了路徑的壓縮
        return parent[x] = find(parent[x]);
    }

    // 合并
    void union_it(int x,int y)
    {
        x = find(x);
        y = find(y);
        // //在同一集合，不需操作
        if(x == y) return ;
        // //rank大的節(jié)點(diǎn)作為合并后的根節(jié)點(diǎn) 
        if(rank[x] < rank[y]) parent[x] = y;
        else {
            // //如果兩個(gè)樹高度一樣，則合并后樹的高度加1
            if(rank[x] == rank[y]) ++rank[x];
            parent[y] = x;
        }
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        init(n);
        for(int i = 0;i < n;++i)
        {
            for(int j = i+1;j < n;++j)
            {
                // 合并兩個(gè)不同的節(jié)點(diǎn)
                if(isConnected[i][j] == 1) union_it(i,j);
            }
        }
        int sum = 0;
        // 統(tǒng)計(jì)數(shù)量
        for(int i = 0;i < parent.size();++i)
            if(parent[i] == i) ++sum;
        return sum;
    }
};

Go實(shí)現(xiàn)

func init_ufs(parent []int,rank []int,n int) {
    for i := 0;i < n;i++ {
        parent[i] = i
        rank[i] = 0
    }
}

func find(parent []int,x int) int {
    if parent[x] == x {
        return x
    }
    parent[x] = find(parent,parent[x])
    return parent[x]
}

func union(parent []int,rank []int,x int,y int) {
    x = find(parent,x)
    y = find(parent,y)
    if x == y {
        return 
    }

    if rank[x] < rank[y] {
        parent[x] = y
    } else {
        if rank[x] == rank[y] {
            rank[x]++
        }
        parent[y] = x
    }
}
func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)
    parent := make([]int,n)
    rank := make([]int,n)
    // init
    init_ufs(parent,rank,n)

    for i := 0; i < n; i++ {
        for j := i+1; j < n; j++ {
            if isConnected[i][j] == 1 {
                union(parent,rank,i,j)
            }
        }
    }
    sum := 0
    for i := 0; i < n; i++ {
        if parent[i]==i {
            sum++
        }
    }
    
    return sum
}

參考：

• 547. 省份數(shù)量 - 力扣（LeetCode）
• 一文搞定并查集_Ding 的博客-CSDN博客