题目链接

LeetCode

题目描述

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

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

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

返回矩阵中 省份 的数量。

示例 1：

547. 省份数量 - 图1

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

示例 2：

547. 省份数量 - 图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]

解题思路

方法一：并查集

计算连通分量数的另一个方法是使用并查集。初始时，每个城市都属于不同的连通分量。遍历矩阵 isConnected，如果两个城市之间有相连关系，则它们属于同一个连通分量，对它们进行合并。

遍历矩阵 isConnected 的全部元素之后，计算连通分量的总数，即为省份的总数。

  1. class Solution {
  2.     int[] parent;
  3.     public int findCircleNum(int[][] isConnected) {
  4.         int n = isConnected.length;
  5.         if(n == 0){
  6.             return 0;
  7.         }
  8.         // 初始化
  9.         this.parent = new int[n];
  10.         for(int i = 0; i < n; ++i){
  11.             parent[i] = i;
  12.         }
  13.         // 合并并查集
  14.         for(int i = 0; i < n; ++i){
  15.             for(int j = i + 1; j < n; ++j){
  16.                 if(isConnected[i][j] == 1){
  17.                     union(i, j);
  18.                 }
  19.             }
  20.         }
  21.         int provinces = 0;
  22.         for(int i = 0; i < n; ++i){
  23.             // 记录存在多少祖先结点
  24.             if(parent[i] == i){
  25.                 ++provinces;
  26.             }
  27.         }
  28.         return provinces;
  29.     }
  30.     // 查询
  31.     private int find(int i){
  32.         if(parent[i] == i){
  33.             return i;
  34.         }else{
  35.             parent[i] = find(parent[i]);
  36.         }
  37.         return parent[i];
  38.     }
  39.     // 合并
  40.     private void union(int i, int j){
  41.         int i_parent = find(i);
  42.         int j_parent = find(j);
  43.         parent[i_parent] = j_parent;
  44.     }
  45. }
  • 时间复杂度 O(n^2log n)

  • 空间复杂度 O(n)

    方法二：深度优先搜索

    1. class Solution {
    2.   public int findCircleNum(int[][] isConnected) {
    3.       int cities = isConnected.length;
    4.       // 该城市是否被访问
    5.       boolean[] visited = new boolean[cities];
    6.       int provinces = 0;
    7.       for (int i = 0; i < cities; i++) {
    8.           // 未被访问
    9.           if (!visited[i]) {
    10.               dfs(isConnected, visited, cities, i);
    11.               provinces++;
    12.           }
    13.       }
    14.       return provinces;
    15.   }
    17.   public void dfs(int[][] isConnected, boolean[] visited, int cities, int i) {
    18.       // 遍历这个城市相连的城市
    19.       for (int j = 0; j < cities; j++) {
    20.           // 如果当前相连的城市未被访问，访问该城市并遍历与该城市相连的城市
    21.           if (isConnected[i][j] == 1 && !visited[j]) {
    22.               visited[j] = true;
    23.               dfs(isConnected, visited, cities, j);
    24.           }
    25.       }
    26.   }
    27. }

  • 时间复杂度 O(n^2)

  • 空间复杂度 O(n)