【Day 76 】2021-11-24 - 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]

[Victoria011]

思路

使用dfs遍历所有相连的node 然后将遍历过的加入seen

代码

def findCircleNum(self, A):
    N = len(A)
    seen = set()
    def dfs(node):
        for nei, adj in enumerate(A[node]):
            if adj and nei not in seen:
                seen.add(nei)
                dfs(nei)

    ans = 0
    for i in range(N):
        if i not in seen:
            dfs(i)
            ans += 1
    return ans

复杂度

Time complexity: O(n^2)

Space complexity: O(n)

[jaysonss]

思路

使用并查集模板

class Solution {
    Map<Integer,Integer> parents = new HashMap<>();

    int count = 0;

    public int findCircleNum(int[][] isConnected) {
         for(int i=0;i<isConnected.length;i++){
             parents.put(i,i);
         }
         count = isConnected.length;

        for(int i=0;i<isConnected.length;i++){
            for(int j=0;j<isConnected.length;j++){
                if(isConnected[i][j] == 1){
                    union(i,j);
                }
            }
        }
        return count;
    }

    int find(int x){
        if(parents.get(x)!=x){
            int root =  find(parents.get(x));
            parents.put(x,root);
            return root;
        } else {
            return x;
        }
    }

    void union(int x, int y){
        int xp = find(x);
        int yp = find(y);
        if(xp == yp)return;
        parents.put(xp,yp);
        count--;
    }

}

[liudi9047]

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

    provinces = 0        

    for i in range(self.n):
        if self.visited[i] == False:
            self.visited[i] = True
            self.dfs(i)
            provinces += 1
            continue                
    return provinces

def dfs(self, i):
    for j in range(self.n):
        if i == j:
            continue

        if self.visited[j] == True:
            continue

        if self.isConnected[i][j] == 0:
            continue

        self.visited[j] = True        

        self.dfs(j)

[HouHao1998]

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

[joriscai]

思路

• 选定一个节点，开始深度优先搜索，将遍历到的节点标记为 visited，直至无法遍历
• 自己、已访问过的、两者无关系的，则不继续遍历

代码

javascript

/*
 * @lc app=leetcode.cn id=547 lang=javascript
 *
 * [547] 省份数量
 */

// @lc code=start
/**
 * @param {number[][]} isConnected
 * @return {number}
 */
var findCircleNum = function(isConnected) {
  function dfs(i) {
    for (let j = 0; j < isConnected.length; j++) {
      const node = isConnected[i][j];
      // 自己不用判断
      // 已经访问过
      if (i !== j && !visited[j] && node) {
        visited[j] = 1
        dfs(j)
      }
    }
  }

  const visited = Array.from({ length: isConnected.length }).fill(0)
  let ret = 0
  for (let i = 0; i < visited.length; i++) {
    if (!visited[i]) {
      visited[i] = 1
      dfs(i)
      ret++
    }
  }

  return ret
};
// @lc code=end

复杂度分析

• 时间复杂度：O(n n)，n n的矩阵
• 空间复杂度：O(n)，只有n个

[itsjacob]

Intuition

• [tags] disjoint set

Implementation

class Solution
{
  class DisjointSet
  {
  private:
    std::vector<int> id;
    std::vector<int> sz;

    int find_recursive_(int x)
    {
      // path compression: flatten the uptree by pointing directly to the set id element
      if (id[x] != x) {
        id[x] = find_recursive_(id[x]);
      }
      return id[x];
    }

    int find_iterative_(int x)
    {
      while (id[x] != x) {
        // update id[x] to its grandparent, this is where the iterative log time complexity comes in
        // the tree height is decreased by a factor of 2
        id[x] = id[id[x]];
        x = id[x];
      }
      return id[x];
    }

  public:
    DisjointSet(int n)
    {
      id.resize(n);
      sz.resize(n);
      std::iota(id.begin(), id.end(), 0);
      std::fill(sz.begin(), sz.end(), 1);
    }

    // union is reserved keyword in cpp, so we rename it as unite
    void unite(int x, int y)
    {
      int xId = find(x);
      int yId = find(y);
      if (xId == yId) return;
      // smart union: merge smaller uptree onto bigger uptree
      if (sz[xId] < sz[yId]) {
        id[xId] = id[yId];
        sz[yId] += sz[xId];
      } else {
        id[yId] = id[xId];
        sz[xId] += sz[yId];
      }
      return;
    }

    int find(int x) { return find_recursive_(x); }

    bool connected(int x, int y) { return find(x) == find(y); }
  };

public:
  int findCircleNum(vector<vector<int>> &isConnected)
  {
    int n = isConnected.size();
    DisjointSet ds(n);

    // build the uptree
    for (int jj = 0; jj < n; jj++) {
      for (int ii = jj + 1; ii < n; ii++) {
        if (isConnected[jj][ii]) {
          ds.unite(jj, ii);
        }
      }
    }

    // count the id nodes from the uptrees
    int res{ 0 };
    for (int ii = 0; ii < n; ii++) {
      if (ds.find(ii) == ii) {
        res++;
      }
    }
    return res;
  }
};

Complexity

• Time complexity: O(N^2logN), where log* is the iterative log, each union/find operation is log\ cost, we have N^2 union operations for building the disjoint set
• Space complexity: O(N) for disjoint set to store the ids and sizes

[q815101630]

并查集

并查集是一个很简单但是高效的数据结构，需要掌握。这道题只需要把所有node加入并查集，然后发现如果两个node联通，就联通两个disjoint set， 独立set cnt -=1

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

        for i in range(len(isConnected)):
            uf.add(i)

        for i in range(len(isConnected)):
            for j in range(len(isConnected)):
                if i != j and isConnected[i][j] == 1:
                    uf.union(i, j)

        return uf.cnt

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}
        self.cnt = 0

    def add(self, x):
        if x not in self.parent:
            self.parent[x] = x
            self.cnt += 1
            self.rank[x] = 1

    # try to find the parent of x
    def find(self, x):
        if x != self.parent[x]:
            # Recursively calls `find` of the parent[x] 
            # And set the output parent to be the one we have found (presume we have found)
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
        return x

    def connected(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        parent_x = self.find(x)
        parent_y = self.find(y)

        if parent_x == parent_y:
            return None
        if self.rank[parent_x] <= self.rank[parent_y]:
            if self.rank[parent_y] == self.rank[parent_x]:
                self.rank[parent_y] += 1

            self.parent[parent_x] = parent_y
        else:
            self.parent[parent_y] = parent_x

        self.cnt -= 1

时间： O(n^2) 需要遍历整个 matrix，并查集操作接近O(n) 空间：O(n)