【Day 76 】2022-06-15 - 547. 省份数量

[azl397985856]

547. 省份数量

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/number-of-provinces/

前置知识

暂无

题目描述

有 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]

[JiangWenqi]

cpp

const int N = 210;
class Solution {
private:
  int p[N];
  int find(int x) {
    if (p[x] != x)
      p[x] = find(p[x]);
    return p[x];
  }

public:
  int findCircleNum(vector<vector<int>> &isConnected) {
    int n = isConnected.size();
    for (int i = 0; i < n; i++)
      p[i] = i;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < isConnected[i].size(); j++) {
        if (isConnected[i][j])
          p[find(i)] = find(j);
      }
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
      if (p[i] == i)
        res++;
    }
    return res;
  }
};

[houmk1212]

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionSet unionSet = new UnionSet(n);
        for (int i = 0; i < n; i++) {
            int[] tmp = isConnected[i];
            for (int j = 0; j < n; j++) {
                if (tmp[j] == 1 && i != j) {
                    unionSet.union(i, j);
                }
            }
        }
        return unionSet.cnt;
    }
}

class UnionSet {
    int[] parent;
    int cnt = 0;

    public UnionSet(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            cnt++;
        }
    }

    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        parent[i] = this.find(parent[i]);
        return parent[i];
    }

    public void union(int x, int y) {
        if (find(x) == find(y)) {
            return;
        }
        parent[find(y)] = find(x);
        cnt--;
    }
}

[xingchen77]

    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def dfs(i):
            visited.add(i)
            for j in range(len(isConnected[i])):
                if j not in visited and isConnected[i][j]==1:
                    dfs(j)

        visited = set()
        provinces = 0
        for i in range(len(isConnected)):
            if i not in visited:
                dfs(i)
                provinces +=1
        return provinces

[ghost]

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        visited = set()
        provinces = 0 

        def dfs(i):
            visited.add(i)
            for j in range(len(isConnected[i])):
                if j not in visited and isConnected[i][j] == 1:
                    dfs(j)

        for i in range(n):
            if i not in visited:
                dfs(i)
                provinces += 1

        return provinces

[MichaelXi3]

Idea

Number of DFS to count the number of disjoint subsets

Code

class Solution {

    public void dfs(boolean[] visited, int[][] isConnected, int i) {
        int[] curNodeReleVant = isConnected[i];
        visited[i] = true;
        for (int j=0; j < curNodeReleVant.length; j++) {
            if (!visited[j] && curNodeReleVant[j] == 1) {
                dfs(visited, isConnected, j);
            }
        }
        return;
    }

    public int findCircleNum(int[][] isConnected) {
        int numNode = isConnected.length;
        int count = 0;
        boolean[] visited = new boolean[numNode];

        for (int i=0; i < numNode; i++) {
            if (!visited[i]) {
                dfs(visited, isConnected, i);
                count++;
            }
        }
        return count;
    }
}

[currybeefer]

class Solution { public int findCircleNum(int[][] isConnected) { //城市数量 int n = isConnected.length; //表示哪些城市被访问过 boolean[] visited = new boolean[n]; int count = 0; //遍历所有的城市 for(int i = 0; i < n; i++){ //如果当前城市没有被访问过，说明是一个新的省份， //count要加1，并且和这个城市相连的都标记为已访问过， //也就是同一省份的 if(!visited[i]){ dfs(isConnected, visited, i); count++; } } return count; }

public void dfs(int[][] isConnected, boolean[] visited, int i){
    for(int j = 0; j < isConnected.length; j++){
        if(isConnected[i][j] == 1 && !visited[j]){
            //如果第i和第j个城市相连，说明他们是同一个省份的，把它标记为已访问过
            visited[j] = true;
            //然后继续查找和第j个城市相连的城市
            dfs(isConnected, visited, j);
        }
    }
}

}

[asuka1h]

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int ret = 0;
        bool hasConnected = false;
        for(auto i = 0; i < isConnected.size(); ++i){
            for(auto j = 0; j < isConnected[i].size();++j){
                if(isConnected[i][j] == 1){
                    hasConnected = true;
                    DFS(isConnected,j,i);
                }

            }
            if(hasConnected){
                ++ret;
                hasConnected = false;
            }

        }
        return ret;
    }
    void DFS(vector<vector<int>>& isConnected, int col, int row){
        int rowSize = isConnected.size();
        int colSize = isConnected[0].size();
        if(col < 0 || row < 0 || col >= colSize || row >= rowSize || isConnected[row][col] == 0){
            return;
        }
        isConnected[row][col] = 0;
        for(int i = 0; i < isConnected[row].size(); ++i){
            DFS(isConnected, i, col);
        }

    }
};

[ZacheryCao]

Idea

Union Find

Code

class UF:
    def __init__(self, M):
        self.parent = {}
        self.size = {}
        self.cnt = M
        for i in range(M):
            self.size[i] = 1
            self.parent[i] = i

    def find(self, p):
        while p != self.parent[p]:
            self.parent[p] = self.find(self.parent[p])
            return self.parent[p]
        return p

    def connected(self, p, q):
        return self.find(p) == self.find(q)

    def union(self, p, q):
        parent_p = self.find(p)
        parent_q = self.find(q)
        if parent_p == parent_q: return
        if self.size[p] < self.size[q]:
            self.parent[parent_p] = parent_q
            self.size[parent_q] += self.size[parent_p]
        else:
            self.parent[parent_q] = parent_p
            self.size[parent_p] += self.size[parent_q]
        self.cnt -= 1

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        if n < 2:
            return n
        uf = UF(n)
        for i in range(n):
            for j in range(n):
                if isConnected[i][j] == 1 and not uf.connected(i, j):
                    uf.union(i, j)
        return uf.cnt

[Ellie-Wu05]

DFS

代码

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:

        def dfs(i):
            visited.add(i)
            for j in range(len(isConnected)):
                if isConnected[i][j] and j not in visited:
                    dfs(j)

        cnt = 0
        visited = set()

        n = len(isConnected)

        for start in range(n):
            if start not in visited:
                cnt +=1
                dfs(start)

        return cnt

复杂度

时间On^2 空间On

[L-SUI]

/**
 * @param {number[][]} isConnected
 * @return {number}
 */
var findCircleNum = function(isConnected) {
    const provinces = isConnected.length;
    const visited = new Set();
    let circles = 0;
    for (let i = 0; i < provinces; i++) {
        if (!visited.has(i)) {
            dfs(isConnected, visited, provinces, i);
            circles++;
        }
    }
    return circles;
};

const dfs = (isConnected, visited, provinces, i) => {
    for (let j = 0; j < provinces; j++) {
        if (isConnected[i][j] == 1 && !visited.has(j)) {
            visited.add(j);
            dfs(isConnected, visited, provinces, j);
        }
    }
};

[xil324]

class Solution(object):
    def findCircleNum(self, isConnected):
        """
        :type isConnected: List[List[int]]
        :rtype: int
        """
        queue = collections.deque();
        visited = set();
        graph = {i: set() for i in range(len(isConnected))}; 
        for i in range(len(isConnected)):
            for j in range(len(isConnected)):
                if isConnected[i][j] == 1 and i != j:
                    graph[i].add(j);
                    graph[j].add(i);

        ans = 0;
        print(graph)
        for i in range(len(isConnected)): 
            if i not in visited: 
                queue.append(i);
                while queue:
                    curr = queue.popleft();
                    visited.add(curr)
                    for neighbor in graph[curr]:
                        if neighbor in visited:
                            continue;
                        queue.append(neighbor);
                ans += 1;
        return ans;

[freedom0123]

class Solution {
    int[] p;
    int find(int x){
        if(x != p[x]) p[x] = find(p[x]);
        return p[x];
    }
    void union(int x, int y){
        p[find(y)] = find(x);
    }

    public int findCircleNum(int[][] M) {
        int n = M.length;
        p = new int[n];
        for(int i = 0; i < n; i++){
            p[i] = i;
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i != j && M[i][j] == 1){
                    union(i,j);
                }
            }
        }

        int res = 0;
        for(int i = 0; i < n; i++){
            if(p[i] == i) res++;
        }

        return res;
    }
}

[Geek-LX]

6.15

思路：DFS

• 选定一个节点，开始深度优先搜索，将遍历到的节点标记为 visited，直到无法继续遍历，连通图数目加一
• 选取下一个未遍历的节点，重复上述过程，直到所有节点都被遍历

代码：

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:

        def dfs(i):
            visited.add(i)
            for j in range(len(isConnected[i])):
                if j not in visited and isConnected[i][j]==1:
                    dfs(j)

        visited = set()
        provinces = 0
        for i in range(len(isConnected)):
            if i not in visited:
                dfs(i)
                provinces +=1

        return provinces

复杂度分析：

• 时间复杂度：O(n)

• 空间复杂度：O(n)

[ShawYuan97]

思路

• 本体需要找到连通分量个数，那么就可以想到使用并查集，可以使用一个变量来记录连通分量的个数
• 对于并查集类的实现，包括初始化,find,union,connected
• 初始化将每个节点的父节点默认为自身
• find：寻找祖宗节点，可以使用迭代的方法；也可以使用递归的方法，而且进行路径压缩，将查询变成常数时间复杂度
• union：将两个连通分量连接在一起，首先判断是否连通，如果不连通，可以判断两个连通分量的大小，小的接上大的
• connected：判断两个连通分量是否连通

关键点

• 并查集定义和使用
• 连通分量的个数记录

代码

• 语言支持：Python3

Python3 Code:

class UF:
    parent = {}
    cnt = 0
    def __init__(self,n):
        for i in range(n):
            self.parent[i] = i
            self.cnt += 1
    # def find(self,x):
    #     while x != self.parent[x]:
    #         x = self.parent[x]
    #     return x
    def find(self,x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
        return x

    def union(self, p, q):
        if self.connected(p,q): return 
        self.parent[self.find(p)] = self.find(q)
        self.cnt -= 1

    def connected(self,p,q):
        return self.find(p) == self.find(q)

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        """
        省份是由一组直接或间接相连的城市，计算省份的数量
        由于isConnected[i][j] == isConnected[j][i]，说明这是一个无向图，只需要关注矩阵的上半部分即可
        """
        N = len(isConnected)
        # 如何使用并查集 
        # 如何构建并查集
        # find union connected
        uf = UF(N)
        for i in range(N):
            for j in range(i):
                if isConnected[i][j] == 1:
                    uf.union(i,j)
        return uf.cnt

复杂度分析

令 n 为二维数组长度。

• 时间复杂度：$O(logn)$
• 空间复杂度：$O(n)$

[hyh331]

Day76 思路

我是思路：

class Solution {
public:
    //查
    int Find(vector<int>& parent, int index){
        if(parent[index] != index){
            parent[index] = Find(parent, parent[index]);
        }
        return parent[index];
    }
    //合并
    void Union(vector<int>& parent, int index1, int index2){
        parent[Find(parent, index1)] = Find(parent, index2);
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        int cities_nums=isConnected.size();
        vector<int> parent(cities_nums);
        //刚开始互不联通，父节点指向自己,自己为一个连通域
        for(int i = 0; i<cities_nums; i++){
            parent[i]=i;
        }
        //
        for(int i=0; i<cities_nums; i++){
            //这里只搜索右上三角部分就可以了
            for(int j=i+1; j<cities_nums; j++){
                if(isConnected[i][j] == 1){
                    //合并
                    Union(parent, i, j);
                }
            }
        }
        int province=0;
        for(int i=0; i<cities_nums; i++){
            if(parent[i] == i){
                province++;
            }
        }
        return province;
    }
};

复杂度分析

• 时间复杂度：O(n^2*logn), n为城市的数量
• 空间复杂度：O(n)

[wychmod]

思路

并查集

代码

class UF:
    def __init__(self, M):
        self.parent = {}
        self.size = {}
        self.cnt = 0
        # 初始化 parent，size 和 cnt
        # size 是一个哈希表，记录每一个联通域的大小，其中 key 是联通域的根，value 是联通域的大小
        # cnt 是整数，表示一共有多少个联通域
        for i in range(M):
            self.parent[i] = i
            self.cnt += 1
            self.size[i] = 1

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
        return x

    def union(self, p, q):
        if self.connected(p, q): return
        # 小的树挂到大的树上， 使树尽量平衡
        leader_p = self.find(p)
        leader_q = self.find(q)
        if self.size[leader_p] < self.size[leader_q]:
            self.parent[leader_p] = leader_q
            self.size[leader_q] += self.size[leader_p]
        else:
            self.parent[leader_q] = leader_p
            self.size[leader_p] += self.size[leader_q]
        self.cnt -= 1

    def connected(self, p, q):
        return self.find(p) == self.find(q)

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        uf = UF(len(isConnected))
        for i in range(len(isConnected)):
            for j in range(len(isConnected[i])):
                if isConnected[i][j]:
                    uf.union(i, j)
        return uf.cnt

[carterrr]

package redo.mistakescollection;

public class 省份数量_547 {

public static void main(String[] args) {

int[][] isConnected =   {{1,1,1},{1,1,1},{1,1,1}};
省份数量_547 s = new 省份数量_547();
s.findCircleNum(isConnected);

}

public int findCircleNum(int[][] isConnected) { final int len = isConnected.length; UF uf = new UF(len); for (int i = 0; i < len; i++) { for(int j = 0; j < i; j++) { // i = j时没有union的意义 if(isConnected[i][j] == 1) uf.union(i, j); } } return uf.size; }

class UF { int[] root; int size;

public UF(int n) {
  this.root = new int[n];
  this.size = n + 1;
  for (int i = 0; i < n; i++) {
    root[i] = i;
  }
}

public void union(int p , int q) {
  int pr = findRoot(p);
  int qr = findRoot(q);
  if(pr != qr) {
    root[pr] = qr; // 这里应该把所有根为p 或者其他pr的改为qr  但是把路径压缩放到findRoot也行
    this.size --;
  }

}

public int findRoot(int r) { // 路径压缩  下次查找的时候把 真正的根节点赋值过来
  if(root[r] == r) return r;
  return root[r] = findRoot(root[r]);
}

} }

[Shuchunyu]

class Solution { public int findCircleNum(int[][] isConnected) { int cities = isConnected.length; boolean[] visited = new boolean[cities]; int provinces = 0; for (int i = 0; i < cities; i++) { if (!visited[i]) { dfs(isConnected, visited, cities, i); provinces++; } } return provinces; }

public void dfs(int[][] isConnected, boolean[] visited, int cities, int i) {
    for (int j = 0; j < cities; j++) {
        if (isConnected[i][j] == 1 && !visited[j]) {
            visited[j] = true;
            dfs(isConnected, visited, cities, j);
        }
    }
}

}

[LQyt2012]

思路

并查集

代码

class UnionFind:
    def __init__(self):
        self.father = {}
        # 额外记录集合的数量
        self.num_of_sets = 0

    def find(self,x):
        root = x

        while self.father[root] != None:
            root = self.father[root]

        while x != root:
            original_father = self.father[x]
            self.father[x] = root
            x = original_father

        return root

    def merge(self,x,y):
        root_x,root_y = self.find(x),self.find(y)

        if root_x != root_y:
            self.father[root_x] = root_y
            # 集合的数量-1
            self.num_of_sets -= 1

    def add(self,x):
        if x not in self.father:
            self.father[x] = None
            # 集合的数量+1
            self.num_of_sets += 1

class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        uf = UnionFind()
        for i in range(len(M)):
            uf.add(i)
            for j in range(i):
                if M[i][j]:
                    uf.merge(i,j)

        return uf.num_of_sets

复杂度分析

时间复杂度：O(N*NlogN)
空间复杂度：O(N)

[MoonLee001]

var findCircleNum = function(isConnected) {
    const cities = isConnected.length;
    const visited = new Set();
    let provinces = 0;
    for (let i = 0; i < cities; i++) {
        if (!visited.has(i)) {
            dfs(isConnected, visited, cities, i);
            provinces++;
        }
    }
    return provinces;
};

const dfs = (isConnected, visited, cities, i) => {
    for (let j = 0; j < cities; j++) {
        if (isConnected[i][j] == 1 && !visited.has(j)) {
            visited.add(j);
            dfs(isConnected, visited, cities, j);
        }
    }
};

[zhishinaigai]

class Solution {
public:
    void dfs(vector<vector<int>>& isConnected,vector<int>& visitied,int cities,int i){
        for(int j=0;j<cities;++j){
            if(isConnected[i][j]&&!visitied[j]){
                visitied[j]=1;
                dfs(isConnected,visitied,cities,j);
            }
        }
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        int cities=isConnected.size();
        vector<int> visitied(cities);
        int pro=0;
        for(int i=0;i<cities;++i){
            if(!visitied[i]){
                dfs(isConnected,visitied,cities,i);
                pro++;
            }
        }
        return pro;
    }
};

[revisegoal]

uf

uf加入成员变量cnt，cnt初始化为n，每次union减1

class Solution {
    class UF {
        int[] parent;
        int[] size;
        int cnt;
        UF(int n) {
            parent = new int[n];
            size = new int[n];
            cnt = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        void union(int p, int q) {
            int pRoot = find(p);
            int qRoot = find(q);
            if (pRoot == qRoot) {
                return;
            }
            if (size[pRoot] < size[qRoot]) {
                parent[pRoot] = qRoot;
                size[qRoot]++;
            } else {
                parent[qRoot] = pRoot;
                size[pRoot]++;
            }
            cnt--;
        }
        int find(int p) {
            while (parent[p] != p) {
                p = parent[p];
            }
            return p;
        }
    }

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UF uf = new UF(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    uf.union(i, j);
                } 
            }
        }
        return uf.cnt;
    }
}

• time: O(n ^ 2)
• space: O(n)

[djd28176]

class Solution {

    public int findCircleNum(int[][] isConnected) {
        int[] visited = new int[isConnected.length];
        int count = 0;
        for(int row = 0; row < isConnected.length; row++){
            if(visited[row] == 0){
                dfs(isConnected, visited, row);
                count++;
            }
        }
        return count;
    }
    private void dfs(int[][] isConnected, int[] visited, int row){
        for(int col = 0; col < isConnected.length; col++){
            if(isConnected[row][col] == 1 && visited[col] == 0){
                visited[col] = 1;
                dfs(isConnected, visited, col);
            }
        }
    }
}

[miss1]

代码

var findCircleNum = function(isConnected) {
  let parent = {}, n = isConnected.length, count = n;
  for (let i = 0; i < n; i++) parent[i] = i;

  const find = function(x) {
    if (x !== parent[x]) {
      parent[x] = find(parent[x]);
      return parent[x];
    }
    return x;
  };

  const union = function (p, q) {
    let root1 = find(p), root2 = find(q);
    if (root1 === root2) return;
    parent[root1] = root2;
    count--;
  };

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (isConnected[i][j] === 1) {
        union(i, j);
      }
    }
  }

  return count;
};

复杂度

• time: O(nlogn) n为矩阵isConnected的大小
• space: O(n)

[maggiexie00]

def __init__(self):
    self.father = {}
    self.num_of_sets = 0

def find(self,x):
    root = x

    while self.father[root] != None:
        root = self.father[root]

    while x != root:
        original_father = self.father[x]
        self.father[x] = root
        x = original_father

    return root

def merge(self,x,y):
    root_x,root_y = self.find(x),self.find(y)

    if root_x != root_y:
        self.father[root_x] = root_y
        self.num_of_sets -= 1

def add(self,x):
    if x not in self.father:
        self.father[x] = None
        self.num_of_sets += 1

def findCircleNum(self, M: List[List[int]]) -> int:
    uf = UnionFind()
    for i in range(len(M)):
        uf.add(i)
        for j in range(i):
            if M[i][j]:
                uf.merge(i,j)

    return uf.num_of_sets

[taojin1992]

// time: O(n^2)
// space: O(n)

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UF unionFindObj = new UF(n);  // O(n) time
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {  
                if (isConnected[i][j] == 1) {
                    unionFindObj.union(i, j); // union O(1)
                }
            }
        }
        return unionFindObj.numOfUnions;
    }

    class UF {
        int numOfUnions;
        int[] parent;
        int[] size;

        UF(int n) {
            numOfUnions = n;
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        int find(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]]; 
                x = parent[x];
            }
            return x;
        }

        boolean connected(int p, int q) {
            return find(p) == find(q);
        }

        void union(int p, int q) {
            int headOfP = find(p);
            int headOfQ = find(q);
            if (headOfP == headOfQ) {
                return;
            }
            if (size[headOfP] < size[headOfQ]) {
                // attach headOfP to headOfQ
                parent[headOfP] = headOfQ;
                size[headOfQ] += size[headOfP];
            } else {
                parent[headOfQ] = headOfP;
                size[headOfP] += size[headOfQ];
            }
            numOfUnions -= 1;
        }

    }

}

[xiayuhui231]

const int N = 210; class Solution { private: int p[N]; int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; }

public: int findCircleNum(vector<vector> &isConnected) { int n = isConnected.size(); for (int i = 0; i < n; i++) p[i] = i; for (int i = 0; i < n; i++) { for (int j = 0; j < isConnected[i].size(); j++) { if (isConnected[i][j]) p[find(i)] = find(j); } } int res = 0; for (int i = 0; i < n; i++) { if (p[i] == i) res++; } return res; } };

[Yongxi-Zhou]

思路

Union Find

代码

    class Solution:
        def findCircleNum(self, isConnected: List[List[int]]) -> int:
            n = len(isConnected)
            dsu = DSU(n)
            res = n
            count = 0
            for i in range(n):
                for j in range(n):
                    if i == j:
                        continue
                    if isConnected[i][j] == 1 and dsu.find(i) != dsu.find(j):
                        dsu.union(i, j)
                        res -= 1
            return res

    class DSU:
        def __init__(self, n):
            self.parent = [i for i in range(n + 1)]

        def find(self, x):
            if x != self.parent[x]:
                self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

        def union(self, x, y):
            self.parent[self.find(x)] = self.find(y)

复杂度

time O(n ^ 3) space O(n)