LeetCode_并查集_DFS_BFS_中等_547.省份数量

素颜马尾好姑娘i 2023-10-06 23:52 7阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

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

返回矩阵中省份的数量。

**示例 1：**  
![在这里插入图片描述][49654a87686a465693d1ed6330acbafa.png]  
输入：isConnected = \[\[1,1,0\],\[1,1,0\],\[0,0,1\]\]  
输出：2

**示例 2：**  
![在这里插入图片描述][fa254bd2e6e84cf8968d9402e8c65507.png]  
输入：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\]

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/number-of-provinces

## 2.思路 ##

（1）并查集  
分析本题后发现可以直接使用并查集算法，有关并查集算法的模板可以参考[核心框架汇总中的并查集算法][Link 1]，此处就不再赘述。

（2）深度优先搜索 (DFS)  
本题也可以用 DFS 来解决。对于每个城市，如果该城市尚未被遍历过，则从该城市开始进行 DFS，直到该城市所处的连通分量中的所有城市都被遍历到，即可得到一个省份，并用变量 provinces 保存省份的数量（其初始值为 0）。此外，为了在遍历过程防止对城市进行重复遍历，可以用数组 visited 来记录每个城市节点是否被遍历。

（3）广度优先搜索 (BFS)  
本题也可以用 BFS 来解决。对于每个城市，如果该城市尚未被遍历过，则从该城市开始进行 BFS，直到该城市所处的连通分量中的所有城市都被遍历到，即可得到一个省份，并用变量 provinces 保存省份的数量（其初始值为 0）。此外，为了在遍历过程防止对城市进行重复遍历，可以用数组 visited 来记录每个城市节点是否被遍历。

## 3.代码实现（Java） ##

//思路1————并查集
    class Solution {
        
        public int findCircleNum(int[][] isConnected) {
        
            int res = 0;
            int n = isConnected.length;
            UnionFind uf = new UnionFind(n);
            //遍历邻接矩阵
            for (int i = 0; i < n; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (isConnected[i][j] == 1) {
        
                    	//如果第 i 个城市和第 j 个城市直接相连，那么将其连通
                        uf.union(i, j);
                    }
                }
            }
            //连通分量(树)的个数即为本题中省份的数量
            return uf.getCount();
        }
    }
    
    //并查集
    class UnionFind {
        
        //记录连通分量(树)的个数
        private int count;
        //节点 x 的父节点是 parent[x]
        private int[] parent;
        
        //构造函数
        public UnionFind(int n) {
        
            //初始时每个节点都是一个连通分量
            this.count = n;
            parent = new int[n];
            //初始时每个节点的父节点都是其自己，即每棵树中只有一个节点
            for (int i = 0; i < n; i++) {
        
                parent[i] = i;
            }
        }
        
        //将 p 和 q 连通
        public void union(int p, int q) {
        
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP != rootQ) {
        
                parent[rootQ] = rootP;
                // 两个连通分量合并成一个连通分量
                count--;
            }
            //如果 p 和 q 的父节点相同，它们本就是连通的，直接返回即可
        }
        
        //判断 p 和 q 是否互相连通，即判断 p 和 q 是否在同一颗树中
        public boolean isConnected(int p, int q) {
        
            int rootP = find(p);
            int rootQ = find(q);
            //如果 p 和 q 的父节点相同，则说明它们在同一颗树中，即它们是连通的
            return rootP == rootQ;
        }
        
        //查找节点 x 的父节点，同时进行路径压缩，并且在路径压缩时维护数组 parent
        public int find(int x) {
        
            if (parent[x] != x) {
        
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        //返回连通分量(树)的个数
        public int getCount() {
        
            return count;
        }
    }

//思路2————深度优先搜索 (DFS)
    class Solution {
        
        public int findCircleNum(int[][] isConnected) {
        
            // n 表示城市数量
            int n = isConnected.length;
            boolean[] visited = new boolean[n];
            int provinces = 0;
            for (int i = 0; i < n; i++) {
        
                if (!visited[i]) {
        
                    dfs(isConnected, visited, n, i);
                    //城市 i 所处的连通分量中的所有城市都被访问到，此时即可得到一个省份
                    provinces++;
                }
            }
            return provinces;
        }
        
        // DFS
        public void dfs(int[][] isConnected, boolean[] visited, int n, int i) {
        
        	visited[i] = true;
            for (int j = 0; j < n; j++) {
        
                if (isConnected[i][j] == 1 && !visited[j]) {
        
                    visited[j] = true;
                    dfs(isConnected, visited, n, j);
                }
            }
        }
    }

//思路3————广度优先搜索 (BFS)
    class Solution {
        
        public int findCircleNum(int[][] isConnected) {
        
            // n 表示城市数量
            int n = isConnected.length;
            //定义 visited 数组，防止对节点进行重复遍历
            boolean[] visited = new boolean[n];
            //省份数量，初始化为 0
            int provinces = 0;
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < n; i++) {
        
                if (!visited[i]) {
        
                    //城市 i 未被访问过，从其开始 BFS
                    queue.offer(i);
                    visited[i] = true;
                    while (!queue.isEmpty()) {
        
                        int j = queue.poll();
                        visited[j] = true;
                        //将与城市 j 相连的城市加入到 queue 中
                        for (int k = 0; k < n; k++) {
        
                            if (isConnected[j][k] == 1 && !visited[k]) {
        
                                queue.offer(k);
                            }
                        }
                    }
                    //城市 i 所处的连通分量中的所有城市都被访问到，此时即可得到一个省份
                    provinces++;
                }
            }
            return provinces;
        }
    }

[49654a87686a465693d1ed6330acbafa.png]: https://img-blog.csdnimg.cn/49654a87686a465693d1ed6330acbafa.png
[fa254bd2e6e84cf8968d9402e8c65507.png]: https://img-blog.csdnimg.cn/fa254bd2e6e84cf8968d9402e8c65507.png
[Link 1]: https://labuladong.gitee.io/algo/1/