【Day 76 】2022-02-25 - 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]

[charlestang]

思路

并查集

如果 i 和 j 是连接的，那么将 i 和 j 进行 UNION 操作。同时将总节点数减少 1。

最后剩下的节点数，就是答案。

代码

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        parent = [i for i in range(n)]

        def find(x: int):
            if parent[x] == x:
                return x
            return find(parent[x])

        cnt = n
        def union(x: int, y: int):
            px = find(x)
            py = find(y)

            if px != py:
                parent[px] = py
                nonlocal cnt
                cnt -= 1

        for i in range(n - 1):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1:
                    union(i, j)

        return cnt

时间复杂度，用了最朴素的写法，没有任何优化 O(n)

空间复杂度 O(n)

[chakochako]

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

[xuhzyy]

class UnionFind:
    def __init__(self):
        self.father = {}
        self.count = 0

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

    def find(self, x):
        root = x
        while(self.father[root] != root):
            root = self.father[root]

        while(x != root):
            orifather = self.father[x]
            self.father[x] = root
            x = orifather

        return root

    def merge(self, x, y):
        rootx, rooty = self.find(x), self.find(y)
        if rootx != rooty:
            self.father[rootx] = rooty
            self.count -= 1

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

        uf = UnionFind()

        for i in range(n):
            uf.add(i)

        for i in range(1, n):
            for j in range(i):
                if isConnected[i][j] == 1:
                    uf.merge(i, j)

        return uf.count

[yan0327]

func findCircleNum(isConnected [][]int) int {
    out := 0
    n := len(isConnected)
    parent := make([]int,n)
    for i:= range parent{
        parent[i] = i
    }
    var find func(int)int
    find = func(x int) int{
        if parent[x] != x{
            parent[x] = find(parent[x])
        }
        return parent[x]
    }
    union := func(from,to int){
        parent[find(from)] = find(to)
    }
    for i,row := range isConnected{
        for j:=i+1;j<n;j++{
            if row[j] == 1{
                union(i,j)
            }
        }
    }
    for i,p := range parent{
        if i == p{
            out++
        }
    }
    return out
}

[ZJP1483469269]

class Solution:
    def findCircleNum(self, g: List[List[int]]) -> int:
        n = len(g)
        p = [i for i in range(n)]
        size = n
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        for i in range(n):
            for j in range(i+1,n):  
                if g[i][j]:
                    if find(i) != find(j):
                        p[find(i)] = find(j)
                        size -= 1
        return size

[Tesla-1i]

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        parent = [i for i in range(n)]

        def find(x: int):
            if parent[x] == x:
                return x
            return find(parent[x])

        cnt = n
        def union(x: int, y: int):
            px = find(x)
            py = find(y)

            if px != py:
                parent[px] = py
                nonlocal cnt
                cnt -= 1

        for i in range(n - 1):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1:
                    union(i, j)

        return cntclass Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        parent = [i for i in range(n)]

        def find(x: int):
            if parent[x] == x:
                return x
            return find(parent[x])

        cnt = n
        def union(x: int, y: int):
            px = find(x)
            py = find(y)

            if px != py:
                parent[px] = py
                nonlocal cnt
                cnt -= 1

        for i in range(n - 1):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1:
                    union(i, j)

        return cnt

[iambigchen]

代码

var findCircleNum = function (M) {
  const visited = Array.from({ length: M.length }).fill(0);
  let res = 0;
  for (let i = 0; i < visited.length; i++) {
    if (!visited[i]) {
      visited[i] = 1;
      dfs(i);
      res++;
    }
  }
  return res;

  function dfs(i) {
    for (let j = 0; j < M.length; j++) {
      if (i !== j && !visited[j] && M[i][j]) {
        visited[j] = 1;
        dfs(j);
      }
    }
  }
};

[zjsuper]

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        #dfs
        visited = [False]*len(isConnected)
        ans = 0
        for i in range(len(isConnected)):
            if visited[i] == False:
                visited[i] = True
                ans += 1
                province = [i]
                for p in province:
                    for a,b in enumerate(isConnected[p]):
                        if a not in province and b ==1:
                            province.append(a)
                            visited[a] = True

        return ans

[CoreJa]

思路

并查集的基础题型，回顾学习一波。

• DFS：用DFS搜每个连通的点即可，入参为节点号，dfs和这个节点连通的每个点，设置visited，复杂度$O(n)$
• UF工具类：手写了并查集的工具类，有两个重点：调用查找的时候要记得路径压缩，建议写成递归式的查找；合并时最好按秩合并，即小树往大树身上合并。复杂度$O(n)$
• 嵌入式UF：尝试了不单独写UF工具类(因为看起来像在背UF的代码)的最佳实践，需要抽象出find函数，因为合并一般就一次操作，所以可以直接inline写，复杂度$O(n)$

代码

class UF:
    def __init__(self, n):
        self.uf = {}
        self.size = {}
        self.cnt = 0
        for i in range(n):
            self.uf[i] = i
            self.size[i] = 1
            self.cnt += 1

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

    def union(self, p, q):
        p, q = self.find(p), self.find(q)
        if p != q:
            self.cnt -= 1
            if self.size[p] > self.size[q]:
                self.uf[q] = p
                self.size[p] += self.size[q]
            else:
                self.uf[p] = q
                self.size[q] += self.size[p]

class Solution:
    # DFS：用DFS搜每个连通的点即可，入参为节点号，dfs和这个节点连通的每个点，设置`visited`，复杂度$O(n)$
    def findCircleNum1(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        visited = set()
        ans = 0

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

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

    # UF工具类：手写了并查集的工具类，有两个重点：调用查找的时候要记得路径压缩，建议写成递归式的查找；合并时最好按秩合并，
    # 即小树往大树身上合并。复杂度$O(n)$
    def findCircleNum2(self, isConnected: List[List[int]]) -> int:
        uf = UF(n := len(isConnected))
        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j]:
                    uf.union(i, j)
        return uf.cnt

    # 嵌入式UF：尝试了不单独写UF工具类(因为看起来像在背UF的代码)的最佳实践，需要抽象出`find`函数，因为合并一般就一次操作，
    # 所以可以直接`inline`写，复杂度$O(n)$
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        uf = {}
        size = {}
        ans = n
        for i in range(n):
            uf[i] = i
            size[i] = 1

        def find(x):
            if uf[x] != x:
                uf[x] = find(uf[x])
                return uf[x]
            return x

        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j]:
                    p, q = find(i), find(j)
                    if p != q:
                        ans -= 1
                        if size[p] > size[q]:
                            uf[q] = p
                            size[p] += size[q]
                        else:
                            uf[p] = q
                            size[q] += size[p]
        return ans

[haixiaolu]

class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n
        self.size = n 

        for i in range(n):
            self.parent[i] = i

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.size -= 1
            self.parent[root_x] = root_y

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

[zhangzz2015]

思路

• 图的遍历，可使用dfs bfs，目前采用标准unin find模板。时间复杂度为O(n^2)，空间复杂度为O(n)

关键点

代码

• 语言支持：C++

C++ Code:

class UF
{
public: 
  vector<int> parent; 
  int numComp;   
  UF(int n)
  {
      for(int i=0; i<n; i++)
          parent.push_back(i); 
      numComp = n; 
  }
  void uninTwoNode(int inode, int jnode)
  {
      int iparent = findParent(inode); 
      int jparent = findParent(jnode); 
      if(iparent != jparent)
      {
          parent[iparent] = jparent; 
          numComp --;           
      }
  }
  int findParent(int inode)
  {
      while(parent[inode]!=inode)
      {
          parent[inode]= parent[parent[inode]]; 
          inode = parent[inode]; 
      }
      return inode;       
  }        
}; 
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {

        UF uf(isConnected.size()); 
        for(int i=0; i< isConnected.size(); i++)
        {
            for(int j=0; j< isConnected[i].size(); j++)
            {
                if(isConnected[i][j])
                    uf.uninTwoNode(i,j); 
            }
        }
        return uf.numComp; 

    }
};

[LannyX]

思路

DFS

代码

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

复杂度分析

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

[1149004121]

547. 省份数量

思路

并查集，求集合个数。如果连通，则合并到一个集合。

代码

var findCircleNum = function(isConnected) {
    const n = isConnected.length;
    let parent = new Array(n).fill(1).map((item, index) => index);
    let count = n;

    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;

    function union(i, j){
        if(find(i) === find(j)) return;
        parent[parent[i]] = parent[j];
        count--;
    };

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

复杂度分析

• 时间复杂度：O(N^2) 。
• 空间复杂度：O(N) 。

[Serena9]

代码

class UF:
    def __init__(self, n) -> None:
        self.parent = {i: i for i in range(n)}
        self.size = n

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

    def connect(self, i, j):
        root_i, root_j = self.find(i), self.find(j)
        if root_i != root_j:
            self.size -= 1
            self.parent[root_i] = root_j

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

                if isConnected[i][j]:
                    uf.connect(i, j)
        return uf.size

[james20141606]

Day 762: 547. Number of Provinces (DFS, BFS, union and find)

• Problem Link

  • 547. Number of Provinces

• Ideas

  • use DFS, or BFS, or Union and Find could solve the problem.

• Complexity: hash table and bucket

  • Time: O(N*2**logN)
  • Space: O(N)

• Code

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

        provinces = len(isConnected)
        visited = set()
        circles = 0

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

        return circles

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

        for i in range(provinces):
            if i not in visited:
                Q = collections.deque([i])
                while Q:
                    j = Q.popleft()
                    visited.add(j)
                    for k in range(provinces):
                        if isConnected[j][k] == 1 and k not in visited:
                            Q.append(k)
                circles += 1

        return circles

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def find(index: int) -> int:
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]

        def union(index1: int, index2: int):
            parent[find(index1)] = find(index2)

        provinces = len(isConnected)
        parent = list(range(provinces))

        for i in range(provinces):
            for j in range(i + 1, provinces):
                if isConnected[i][j] == 1:
                    union(i, j)

        circles = sum(parent[i] == i for i in range(provinces))
        return circles

• other resources:

[ivangin]

code:

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

[ivangin]

code:

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

[callmeerika]

思路

并查集

代码

var City = function (n) {
  this.parent = {};
  this.init(n);
};

City.prototype.init = function (n) {
  for (let i = 0; i < n; i++) {
    this.parent[i] = i;
  }
};

City.prototype.find = function (x) {
  while (x != this.parent[x]) x = this.parent[x];
  return x;
};

City.prototype.union = function (x, y) {
  this.parent[this.find(x)] = this.find(y);
};

var findCircleNum = function (isConnected) {
  let cnt = 0;
  const n = isConnected.length;
  const city = new City(n);
  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      if (isConnected[i][j] === 1) {
        city.union(i, j);
      }
    }
  }
  for (let i in city.parent) {
    if (+i === +city.parent[i]) cnt++;
  }
  return cnt;
};

复杂度

时间复杂度：O(n^2logn)
空间复杂度：O(n)

[cszys888]

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

    provinces = len(isConnected)
    visited = set()
    circles = 0

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

    return circles

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

[falconruo]

思路:

并查集

复杂度分析:

• 时间复杂度: O(N^2 * logN)
• 空间复杂度: O(N)

代码(C++):

class UnionFind {
public:
    vector<int> parent;
    int num;
    UnionFind(int n) {
        parent.resize(n + 1);
        for (int i = 0; i < n; i++)
            parent[i] = i;
        num = n;
    }

    int Find(int id) {
        if (parent[id] != id)
            parent[id] = Find(parent[id]);

        return parent[id];
    }

    void Union(int x, int y) {
        int px = Find(x);
        int py = Find(y);

        if (px != py) {
            parent[px] = py;
            num--;
        }
    }
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        UnionFind uf(n);

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j])
                    uf.Union(i, j);
            }
        }

        return uf.num;
    }
};

[JudyZhou95]

class UF:
    def __init__(self, n):
        self.parent = {i: i for i in range(n)}
        self.size = n

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

    def connect(self, i, j):
        root_i, root_j = self.find(i), self.find(j)
        if root_i != root_j:
            self.size -= 1
            self.parent[root_i] = root_j

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        uf =UF(n)

        for i in range(n):
            for j in range(n):
                if isConnected[i][j]:
                    uf.connect(i,j)
        return uf.size

    """
    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
    """

[machuangmr]

代码

class Solution {
    public int findCircleNum(int[][] isConnected) {
        // int[][] isConnected 是无向图的邻接矩阵，n 为无向图的顶点数量
        int n = isConnected.length;
        // 定义 boolean 数组标识顶点是否被访问
        boolean[] visited = new boolean[n];
        // 定义 cnt 来累计遍历过的连通域的数量
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            // 若当前顶点 i 未被访问，说明又是一个新的连通域，则遍历新的连通域且cnt+=1.
            if (!visited[i]) { 
                cnt++;
                dfs(i, isConnected, visited);
            }
        }
        return cnt;
    }

    private void dfs(int i, int[][] isConnected, boolean[] visited) {
        // 对当前顶点 i 进行访问标记
        visited[i] = true;

        // 继续遍历与顶点 i 相邻的顶点（使用 visited 数组防止重复访问）
        for (int j = 0; j < isConnected.length; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                dfs(j, isConnected, visited);
            }
        }
    }
}

[watchpoints]

public class Solution {
    public void dfs(int[][] M, int[] visited, int i) {
        for (int j = 0; j < M.length; j++) {
            if (M[i][j] == 1 && visited[j] == 0) {
                visited[j] = 1;
                dfs(M, visited, j);
            }
        }
    }
    public int findCircleNum(int[][] M) {
        int[] visited = new int[M.length];
        int count = 0;
        for (int i = 0; i < M.length; i++) {
            if (visited[i] == 0) {
                dfs(M, visited, i);
                count++;
            }
        }
        return count;
    }
}

[xjhcassy]

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);
            }
        }
    }
}

[alongchong]

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

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

[yinhaoti]

class UF:
    parent = {}
    cnt = 0
    def __init__(self, M):
        n = len(M)
        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 connected(self, p, q):
        return self.find(p) == self.find(q)

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

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        """
        TC: O(n^3) Union and find ave: O(logn) worst: O(n)
        SC: O(n)
        """

        M = isConnected
        n = len(M)
        uf = UF(M)
        for i in range(n):
            for j in range(i):
                if M[i][j] == 1:
                    uf.union(i, j)
        return uf.cnt

[declan92]

思路

1. 初始化并查集有n个不连通结点;
2. 并查集合并直接相连的两个城市,如果并查集里不连通,则size-1;如果并查集连通,size不变;

java

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        int size = 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)) {
                    size--;
                }
            }
        }
        return size;
    }
}

class UF {
    int[] parent;

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

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

    public boolean union(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        if (xRoot == yRoot) {
            return false;
        }
        parent[xRoot] = yRoot;
        return true;
    }
}

时间:$O(n^2)$
空间:$O(n)$

[hdyhdy]

func findCircleNum(isConnected [][]int) (ans int) {
    n := len(isConnected)
    parent := make([]int, n)
    for i := range parent {
        parent[i] = i
    }
    var find func(int) int
    find = func(x int) int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }
    union := func(from, to int) {
        parent[find(from)] = find(to)
    }

    for i, row := range isConnected {
        for j := i + 1; j < n; j++ {
            if row[j] == 1 {
                union(i, j)
            }
        }
    }
    for i, p := range parent {
        if i == p {
            ans++
        }
    }
    return
}

[yetfan]

思路 求并集

代码

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
            self.num_of_sets -= 1

    def add(self,x):
        if x not in self.father:
            self.father[x] = None
            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^2) 空间 O(n)

[Aobasyp]

思路 并查集

class Solution { 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.size; } private static class UF { int[] parent; int size; public UF(int n) { parent = new int[n]; size = n; for (int i = 0; i < n; i++) { parent[i] = i; } } public int find(int x) { while (parent[x] != x) { x = parent[x]; } return x; } public void union(int x, int y) { if (find(x) != find(y)) { parent[find(x)] = find(y); size--; } } } }

时间复杂度为 O(nlogn) 空间复杂度：O(n)

[guangsizhongbin]

func findCircleNum(isConnected [][]int) (ans int) { n := len(isConnected) parent := make([]int, n) for i := range parent { parent[i] = i }

var find func(int) int
find = func(x int) int {
    if parent[x] != x {
        parent[x] = find(parent[x])
    }
    return parent[x]
}
union := func(form, to int){
    parent[find(form)] = find(to)
}

for i, row := range isConnected{
    for j := i + 1; j < n ; j++{
        if row[j] == 1{
            union(i, j)
        }
    }
}
for i, p := range parent {
    if i == p {
        ans ++
    }
}
return ans

}

[moirobinzhang]

Code:

public class Solution { public int FindCircleNum(int[][] isConnected) { int n = isConnected.Length; UF uf = new UF(n);

    for (int i = 0; i < n -1; i++)
    {
        for ( int j = i + 1; j < n; j++)
        {
            if (isConnected[i][j] == 1)
                uf.Union(i, j);
        }
    }

    return uf.component;        
}

public class UF
{
    public int[] parent;
    public int component;

    public UF(int n)
    {
        parent = new int[n];
        component = n;

        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    public int Find(int x)
    {
        while( x != parent[x])
            x = parent[x];

        return parent[x];
    }

    public void Union(int x, int y)
    {
        int parentX = Find(x);
        int parentY = Find(y);

        if (parentX == parentY)
            return;

        parent[parentX] = parentY;
        component--;
    }
}    

}

[Hacker90]

Code:

public class Solution { public int FindCircleNum(int[][] isConnected) { int n = isConnected.Length; UF uf = new UF(n);

for (int i = 0; i < n -1; i++)
{
    for ( int j = i + 1; j < n; j++)
    {
        if (isConnected[i][j] == 1)
            uf.Union(i, j);
    }
}

return uf.component;        

}

public class UF { public int[] parent; public int component;

public UF(int n)
{
    parent = new int[n];
    component = n;

    for (int i = 0; i < n; i++)
        parent[i] = i;
}

public int Find(int x)
{
    while( x != parent[x])
        x = parent[x];

    return parent[x];
}

public void Union(int x, int y)
{
    int parentX = Find(x);
    int parentY = Find(y);

    if (parentX == parentY)
        return;

    parent[parentX] = parentY;
    component--;
}

}
}

[shamworld]

var findCircleNum = function(isConnected) {
    let n = isConnected.length;
    if (n==0) return 0;
    let visited = {};
    let count = 0;
    let dfs = (i)=>{
        for(let j=0;j<n;j++){
            if(isConnected[i][j]==1&&!visited[j]){
                visited[j] = true;
                dfs(j);
            }
        }
    }
    for(let i=0;i<n;i++){
        if(!visited[i]){
            dfs(i);
            count++;
        }
    }
    return count;
};

[baddate]

class Solution {
public:
    void dfs(vector<vector<int>>& isConnected, vector<int>& visited, int provinces, int i) {
        for (int j = 0; j < provinces; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                visited[j] = 1;
                dfs(isConnected, visited, provinces, j);
            }
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        int provinces = isConnected.size();
        vector<int> visited(provinces);
        int circles = 0;
        for (int i = 0; i < provinces; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, provinces, i);
                circles++;
            }
        }
        return circles;
    }
};

[fornobugworld]

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def dfs(isConnected,visited,i):
            if i in visited:
                return
            visited[i] = 1
            for j,isCon in enumerate(isConnected[i]):
                if isCon == 1:
                    dfs(isConnected,visited,j)
        visited = dict()
        res = 0
        n = len(isConnected)
        for i in range(n):
            if i in visited:
                continue
            res += 1
            dfs(isConnected,visited,i)
        return res

[hx-code]

class Solution: def findCircleNum(self, isConnected: List[List[int]]) -> int: def dfs(isConnected,visited,i): if i in visited: return visited[i] = 1 for j,isCon in enumerate(isConnected[i]): if isCon == 1: dfs(isConnected,visited,j) visited = dict() res = 0 n = len(isConnected) for i in range(n): if i in visited: continue res += 1 dfs(isConnected,visited,i) return res

[GaoMinghao]

代码

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);
            }
        }
    }
}

[zzzpppy]

class Solution {
    public int findCircleNum(int[][] isConnected) {
        // int[][] isConnected 是无向图的邻接矩阵，n 为无向图的顶点数量
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int cnt = 0;  
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                cnt++;
                queue.offer(i);
                visited[i] = true;
                while (!queue.isEmpty()) {
                    int v = queue.poll();
                    for (int w = 0; w < n; w++) {
                        if (isConnected[v][w] == 1 && !visited[w]) {
                            visited[w] = true;
                            queue.offer(w);
                        }
                    }
                }
            }
        }
        return cnt;
    }
} 

[xinhaoyi]

class UnionFind { // 记录父节点 private Map<Integer,Integer> father; // 记录集合的数量 private int numOfSets = 0;

public UnionFind() {
    father = new HashMap<Integer,Integer>();
    numOfSets = 0;
}

public void add(int x) {
    if (!father.containsKey(x)) {
        father.put(x, null);
        numOfSets++;
    }
}

public void merge(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);

    if (rootX != rootY){
        father.put(rootX,rootY);
        numOfSets--;
    }
}

public int find(int x) {
    int root = x;

    while(father.get(root) != null){
        root = father.get(root);
    }

    while(x != root){
        int original_father = father.get(x);
        father.put(x,root);
        x = original_father;
    }

    return root;
}

public boolean isConnected(int x, int y) {
    return find(x) == find(y);
}

public int getNumOfSets() {
    return numOfSets;
}

}

class Solution { public int findCircleNum(int[][] isConnected) { UnionFind uf = new UnionFind(); for(int i = 0;i < isConnected.length;i++){ uf.add(i); for(int j = 0;j < i;j++){ if(isConnected[i][j] == 1){ uf.merge(i,j); } } }

    return uf.getNumOfSets();
}

}

[taojin1992]

// time: O(n^2)
// space: O(n)
// union find with path compression

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;
        }

    }

}

[CodingProgrammer]

思路

并查集

代码

class Solution {
    public int findCircleNum(int[][] isConnected) {
        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) {
                    uf.union(i, j);
                }
            }
        }

        return uf.size;
    }

    class UnionFind {
        int size;
        int[] roots;

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

        private int find(int x) {
            if (x == this.roots[x]) {
                return x;
            }
            return this.roots[x] = find(this.roots[x]);
        }

        private void union(int p, int q) {
            int pRoot = find(p);
            int qRoot = find(q);
            if (pRoot != qRoot) {
                this.roots[pRoot] = qRoot;
                this.size--;
            }
        }
    }
}

复杂度

• 时间复杂度：O(n^2log⁡n)
• 空间复杂度：O(n)

[tian-pengfei]

class UnionFind{

    vector<int> parent;

    //初始化自己是自己的父母
public :
    UnionFind(int n){
        parent.resize(n);

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

    //把两个集合合起来
    void UnionSet(int i, int j){
        parent[find(i)] = find(j);
    }

    int find(int index){

        if(parent[index]!=index){
            //再寻找过程也可以把自己提到最接近根部的服务是，减少以后查询的时间复杂度
            parent[index] = find(parent[index]);
        }
        return parent[index];
    }

};
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {

        int n = isConnected.size();
        UnionFind uf(n);
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                if(isConnected[i][j])
                uf.UnionSet(i,j);
            }
        }
        unordered_set<int> set;
        for (int i = 0; i < n; ++i) {

            set.insert(uf.find(i));
        }
        return set.size();
    }
};

[Alfie100]

DFS解法：

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

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

        n = len(isConnected)
        visited = set()

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

        return ans

[dahaiyidi]

Problem

[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 表示二者不直接相连。

返回矩阵中 省份 的数量。

---

Note

• 简单的并查集，与[1319. 连通网络的操作次数](https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/) 一致。

---

Complexity

• 时间O：O(m*m*α(n))，其中 m是数组 isConnected的长度，α是阿克曼函数的反函数。
• 空间O：n

---

Python

C++

class UnionFind{
public:
    vector<int> size; // set的size， 有时为set 树的高度？
    vector<int> parent; // 父节点
    int n;  // 节点数
    int setCount;// 有多少个set

public:
    UnionFind(int _n): size(_n, 1), parent(_n), n(_n), setCount(_n) {
        iota(parent.begin(), parent.end(), 0);  // 将parent的元素按顺序设置为0，1，2，3，4
    }
    int findset(int x) {
        // 找到根节点
        return x == parent[x] ? x: parent[x] = findset(parent[x]);
    }
    // int findset(int x) {
    //     return parent[x] == x ? x : parent[x] = findset(parent[x]);
    // }

    bool unite(int x, int y){
        x = findset(x);
        y = findset(y);

        // 若已经在同一个set中
        if(x == y){
            return false;
        }
        // 若不在同一个set中，则需要合并
        // 保证size[x] >= size[y]
        if(size[x] < size[y]){
            swap(x, y);
        }
        // 将y的parent设置为x
        parent[y] = x;
        size[x] += size[y];
        setCount--; // set数量-1
        return true; // 合并成功
    }
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        UnionFind uf(isConnected.size());
        for(int i = 0; i < isConnected.size(); i++){
            for(int j = 0; j < isConnected.size(); j++){
                if(isConnected[i][j] == 1){
                    uf.unite(i, j);
                }
            }
        }
        return uf.setCount;
    }
};

From : https://github.com/dahaiyidi/awsome-leetcode