【LeetCode】547. 省份数量_c语言 并查集 力扣547省份数量

题目：547. 省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中isConnected[i][j] = 1表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例 1：

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

示例 2：

输入：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]

解题思路

使用并查集

1. 并：root1和roo2要属于不同集合，将root2连接到root1下面
2. 查：沿着根的位置一直向上查找，直到<0
3. 寻找环数：
   1. 遍历邻接矩阵
   2. 如果两个节点之间存在边，则寻找两个节点隶属的集合，如果不在同一个集合则并入同一集合。
   3. 遍历并查集，找到<0的个数。

代码

class Solution {
public:

// 使用并查集
// 1. 并：root1和roo2要属于不同集合，将root2连接到root1下面
// 2. 查：沿着根的位置一直向上查找，直到<0
// 3. 寻找环数：
//     1. 遍历邻接矩阵
//     2. 如果两个节点之间存在边，则寻找两个节点隶属的集合，如果不在同一个集合则并入同一集合。
//     3. 遍历并查集，找到<0的个数。
    void unionRoot(vector<int>&s, int root1, int root2) {
        if (root1 == root2) return ;
        s[root2] = root1;
    }

    int find(vector<int>& s, int x) {
        while (s[x] >= 0) x = s[x];
        return x;
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        vector<int> s(isConnected.size(), -1);
        for (int i = 0; i < isConnected.size(); i++) {
            for (int j = 0; j < isConnected.size(); j++) {
                if (isConnected[i][j]) {
                    int root1 = find(s, i);
                    int root2 = find(s, j);
                    unionRoot(s, root1, root2);
                }
            }
        }
        int count = 0;
        for (int i = 0; i < isConnected.size(); i++) {
            if (s[i] < 0) count++;
        }
        return count;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39