LeetCode - 547 省份数量

骑猪看日落 2023-09-23 13:04 66阅读 0赞

### 题目来源 ###

[547. 省份数量 - 力扣（LeetCode）][547. _ - _LeetCode]

### 题目描述 ###

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

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

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

返回矩阵中 省份 的数量。

### 示例 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>输入</td> 
   <td>isConnected = [[1,1,0],[1,1,0],[0,0,1]]</td> 
  </tr> 
  <tr> 
   <td>输出</td> 
   <td>2</td> 
  </tr> 
 </tbody> 
</table>

![a6dda98c052b6194e0bb0531a25fcd6d.jpeg][]

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>输入</td> 
   <td>isConnected = [[1,0,0],[0,1,0],[0,0,1]]</td> 
  </tr> 
  <tr> 
   <td>输出</td> 
   <td>3</td> 
  </tr> 
 </tbody> 
</table>

![528aa849f9d7a20af1f76376fc60a4ad.jpeg][]

### 提示 ###

*  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\]

### 题目解析 ###

此题和[华为机试 - 发广播\_伏城之外的博客-CSDN博客][- _-CSDN]

相同，题解轻看上面连接对应的题目

### 算法源码 ###

/**
     * @param {number[][]} isConnected
     * @return {number}
     */
    var findCircleNum = function (isConnected) {
      const n = isConnected.length;
    
      const ufs = new UnionFindSet(n)
    
      for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
          if (isConnected[i][j] === 1) {
            ufs.union(i, j);
          }
        }
      }
    
      return ufs.count;
    };
    
    class UnionFindSet {
      constructor(n) {
        this.fa = [];
        this.init(n)
        this.count = n;
      }
    
      init(n) {
          for(let i=0; i<n; i++) this.fa[i] = i
      }
     
      find(x) {
        if (x !== this.fa[x]) {
          this.fa[x] = this.find(this.fa[x]);
          return this.fa[x];
        }
        return x;
      }
     
      union(x, y) {
        let x_fa = this.find(x);
        let y_fa = this.find(y);
     
        if (x_fa !== y_fa) {
          this.fa[y_fa] = x_fa;
          this.count--;
        }
      }
    }

![3c7417446f4841818dce9e87d43c5fa3.png][]

[547. _ - _LeetCode]: https://leetcode.cn/problems/number-of-provinces/
[a6dda98c052b6194e0bb0531a25fcd6d.jpeg]: https://img-blog.csdnimg.cn/img_convert/a6dda98c052b6194e0bb0531a25fcd6d.jpeg
[528aa849f9d7a20af1f76376fc60a4ad.jpeg]: https://img-blog.csdnimg.cn/img_convert/528aa849f9d7a20af1f76376fc60a4ad.jpeg
[- _-CSDN]: https://blog.csdn.net/qfc_128220/article/details/127588130?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22127588130%22%2C%22source%22%3A%22qfc_128220%22%7D
[3c7417446f4841818dce9e87d43c5fa3.png]: https://img-blog.csdnimg.cn/3c7417446f4841818dce9e87d43c5fa3.png