【Day 76 】2023-04-30 - 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]

[RestlessBreeze]

code

class Solution {
public:
    void bfs(const vector<vector<int>>& isConnected, vector<int>& visited, int i)
    {
        stack<int> stk;
        stk.push(i);
        visited[i] = 1;
        while (!stk.empty())
        {
            int temp = stk.top();
            stk.pop();
            for (int p = 0; p < isConnected.size(); p++)
            {
                if (visited[p] == 0 && isConnected[temp][p] == 1)
                {
                    stk.push(p);
                    visited[p] = 1;
                }
            }
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        int m = isConnected.size();
        vector<int> visited(m, 0);
        int res = 0;
        for (int i = 0; i < m; i++)
        {
            if (visited[i] == 0)
            {
                res++;
                bfs(isConnected, visited, i);
            }
        }
        return res;
    }
};

[zhangyu1131]

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        // 初始化并查集
        parent_map_.clear();
        for (int i = 0; i < n; ++i)
        {
            parent_map_[i + 1] = i + 1;
        }

        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                if (isConnected[i][j] == 1)
                {
                    if (find(i + 1) != find(j + 1))
                    {
                        union_map(i + 1, j + 1);
                    }
                }
            }
        }

        set<int> res_set;
        for (auto& pair : parent_map_)
        {
            if (res_set.count(pair.second) == 0)
            {
                res_set.insert(pair.second);
            }
        }

        return res_set.size();
    }

private:
    // 并查集
    int find(int node)
    {
        if (parent_map_[node] != node)
        {
            parent_map_[node] = find(parent_map_[node]);
        }
        return parent_map_[node];
    }

    void union_map(int node1, int node2)
    {
        if (find(node1) == find(node2))
        {
            return;
        }
        int parent_1 = find(node1);
        int parent_2 = find(node2);
        if (parent_1 < parent_2)
        {
            parent_map_[parent_2] = parent_1;
            for (auto& pair : parent_map_)
            {
                if (pair.second == parent_2)
                {
                    pair.second = parent_1;
                }
            }
        }
        else
        {
            parent_map_[parent_1] = parent_2;
            for (auto& pair : parent_map_)
            {
                if (pair.second == parent_1)
                {
                    pair.second = parent_2;
                }
            }
        }
    }

private:
    map<int, int> parent_map_;
};

[Diana21170648]

思路

并查集，先搜索，再连接，如根节点不一致，则计数减一

class UF:
    def __init__(self,n)->None:
        self.parent={i:i for i in range(n)}#使用字典推导式构造一个字典self.parent,键和值都是从0到n-1的整数
        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#把j作为i的根节点

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

**复杂度分析**
- 时间复杂度：O(NlogN)，使用路径压缩。
- 空间复杂度：O(N)

[NorthSeacoder]

/**
 * @param {number[][]} isConnected
 * @return {number}
 */
var findCircleNum = function (isConnected) {
    const uf = {};
    let count = 0;
    const add = (city) => {
        if (!uf[city] && uf[city] !== 0) {
            uf[city] = city;
            count++
        }
    }
    const find = (city) => {
        if (uf[city] !== city) {
            uf[city] = find(uf[city]);
            return uf[city]
        }
        return city
    };
    const connected = (a, b) => {
        return find(a) === find(b)
    }
    const union = (a, b) => {
        if (!connected(a, b)) {
            uf[find(a)] = find(b);
            count--;
        }
    }
    for (let i = 0; i < isConnected.length; i++) {
        for (let j = 0; j < isConnected[0].length; j++) {
            if (isConnected[i][j] === 1) {
                add(i);
                add(j);
                union(i, j)
            }
        }
    };
    return count
};

[snmyj]

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<bool> visited(n, false);
        queue<int> que;

        int ans = 0;
        for(int candi = 0; candi < n; candi++) {
            if(visited[candi] == false) {
                ans++;
                que.push(candi);
                visited[candi] = true;
                while(!que.empty()) {
                    int city = que.front();
                    que.pop();
                    for(int neighbor = 0; neighbor < n; neighbor++) {
                        if(visited[neighbor] == false and isConnected[city][neighbor] == 1) {
                            que.push(neighbor);
                            visited[neighbor] = true;
                        }
                    }
                }
            }
        }
        return ans;
    }
};

[X1AOX1A]

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

[harperz24]

class UnionFind:
    def __init__(self, size: int):
        self.root = [i for i in range(size)]
        self.rank = [1] * size
        self.component_count = size

    def find(self, x: int) -> int:
        if x == self.root[x]:
            return x
        return self.find(self.root[x])

    def union(self, x: int, y: int) -> None:
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
        if self.rank[rx] >= self.rank[ry]:
            self.root[ry] = rx
            rank_up = 1 if self.rank[rx] == self.rank[ry] else 0
            self.rank[rx] += rank_up
        else:
            self.root[rx] = ry
        self.component_count -= 1

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

        # time: O(n**2 * α(n))
        # space: O(n)

[lp1506947671]

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

复杂度分析

令 n 为矩阵 M 的大小。

• 时间复杂度：由于仅使用了一种优化（路径压缩）,因此时间复杂度为 O(nlogn)
• 空间复杂度：O(n)

[FireHaoSky]

思路：并查集

代码：python

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, isConnected: List[List[int]]) -> int:
        uf = UnionFind()
        for i in range(len(isConnected)):
            uf.add(i)
            for j in range(i):
                if isConnected[i][j]:
                    uf.merge(i,j)
        return uf.num_of_sets

复杂度分析：

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

[JasonQiu]

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        visited = defaultdict(int)
        result = 0

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

        for i in range(len(isConnected)):
            if not visited[i]:
                dfs(i)
                result += 1
        return result

Time: O(n^2) Space: O(n)

[Lydia61]

547. 省份数量

思路

深度优先

代码

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

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

[aswrise]

class Solution:
    def findCircleNum(self, M):
        class Union:
            def __init__(self, n):
                self.cnt = n
                self.parent = [i for i in range(n)]

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

            def union(self, a, b):
                a_root = self.find(a)
                b_root = self.find(b)
                if a_root == b_root: return
                if a_root < b_root:
                    self.parent[b_root] = a_root
                else:
                    self.parent[a_root] = b_root
                self.cnt -= 1    

            def get_count(self):
                return self.cnt

        ut = Union(len(M))
        for i in range(len(M)):
            for j in range(len(M[0])):
                if M[i][j] == 1:
                    ut.union(i, j)

        return ut.get_count()

[Jetery]

class Solution {
public:
    int ans, a[210];

    void init(int n) {
        for (int i = 0; i < n; i++) a[i] = i;
    }

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

    void connect(int i, int j) {
        int x = find(i), y = find(j);
        if (x == y) return;
        a[x] = y;
        ans--;
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        int row = isConnected.size();
        int col = isConnected[0].size();
        init(row);
        ans = row;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (isConnected[i][j]) connect(i, j);
            }
        }
        return ans;
    }
};

[yingchehu]

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

[kangliqi1]

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

}

[tzuikuo]

思路

并查集

代码

class Solution {
public:
    vector<int> g[205];
    int n, m, vis[205];

    void dfs(int u) {
        vis[u] = 1;
        for(auto v: g[u]) {
            if(!vis[v]) dfs(v);
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        memset(vis, 0, sizeof(vis));
        n = isConnected.size(), m = isConnected[0].size();
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(isConnected[i][j]) {
                    g[i].push_back(j);
                }
            }
        }

        int ans = 0;
        for(int u=0; u<n; u++) {
            if(!vis[u]) {
                ans++;
                dfs(u);
            }
        }
        return ans;
    }
};

复杂度分析 -待定

[joemonkeylee]

思路

dfs

代码

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

复杂度分析

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

[bookyue]

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;

            dfs(isConnected, i, visited);
            count++;
        }

        return count;
    }

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

[kofzhang]

思路

深度优先搜索

复杂度

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

代码

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        d = {}
        s = set(range(len(isConnected)))
        @lru_cache(None)
        def dfs(k,n):
            if k not in s:
                return
            if n not in d:
                d[n]=[n]
            s.remove(k)
            for i in range(len(isConnected)):
                if isConnected[k][i] == 1:   
                    d[n].append(i)                                        
                    dfs(i,n)
        for a in range(len(isConnected)):
            dfs(a,a)
        return len(d)

[chanceyliu]

代码

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

function findCircleNum(isConnected: number[][]): number {
  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;

};

复杂度分析

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