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

[snmyj]

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

[guowei0223]

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        #bfs
        res = 0
        n = len(isConnected)
        visited =[0] * n
        que = deque()
        for i in range(n):
            if visited[i] == 0:
                que.append(i)
                visited[i] = 1
                res += 1
                while que:
                    c = que.popleft()
                    for j in range(n):
                        if isConnected[c][j] == 1 and visited[j] == 0:
                            visited[j] = 1
                            que.append(j)
        return res

[Abby-xu]

class Solution: def findCircleNum(self, isConnected: List[List[int]]) -> int: def dfs(n) : for i, v in enumerate(isConnected[n]) : if v == 1 and i not in seen : seen.add(i) dfs(i)

    l = len(isConnected)
    ans = 0
    seen = set()
    for i in range(l) :
        if i not in seen :
            dfs(i)
            ans += 1
    return ans

[Ryanbaiyansong]

class UF:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1 for _ in range(n)]
        self.count = n

    def union(self, x, y):
        fx = self.find(x)
        fy = self.find(y)
        if fx == fy:
            return 
        if self.size[fx] < self.size[fy]:
            fx, fy = fy, fx 
        self.size[fx] += self.size[fy]
        self.par[fy] = fx 
        self.count -= 1

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

class Solution:
    def findCircleNum(self, a: List[List[int]]) -> int:
        # UF
        n = len(a)
        uf = UF(n)
        for i, row in enumerate(a):
            for j, v in enumerate(row):
                if v:
                    uf.union(i, j)

        return uf.count

[JancerWu]

// 后面再回来补个并查集解法
class Solution {
    int[][] g;
    int n;
    boolean[] visited;
    public int findCircleNum(int[][] isConnected) {
        g = isConnected;
        n = isConnected.length;
        visited = new boolean[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i);
                ans++;
            }
        }
        return ans;
    }
    public void dfs(int i) {
        visited[i] = true;
        for (int j = 0; j < n; j++) {
            if (g[i][j] == 1 && !visited[j]) dfs(j);
        }
    }
}

[bookyue]

code

1. dfs
2. union find

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

    private int[] parent;
    private int[] rank;

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        parent = new int[n];
        rank = new int[n];
        int count = 0;

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

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (isConnected[i][j] == 1)
                    count = union(i, j) ? count + 1 : count;

        return n - count;
    }

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

    private boolean union(int p, int q) {
        int qRoot = find(q);
        int pRoot = find(p);

        if (qRoot == pRoot) return false;

        if (rank[pRoot] >= rank[qRoot])
            parent[qRoot] = parent[pRoot];
        else
            parent[pRoot] = parent[qRoot];

        if (rank[pRoot] == rank[qRoot])
            rank[pRoot]++;

        return true;
    }

[JancerWu]

// 补充并查集解法
class Solution {

    class Union{
        int[] root;
        Union(int n) {
            root = new int[n];
            for (int i = 0; i < n; i++) root[i] = i;
        }
        public int findRoot(int x) {
            if (root[x] == x) return x;
            return root[x] = findRoot(root[x]);
        }
        public void combine(int x, int y) {
            root[findRoot(x)] = root[findRoot(y)];
        }
    }

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        Union union = new Union(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isConnected[i][j] == 1) union.combine(i, j);
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (union.root[i] == i) ans++;
        }
        return ans;
    }

}

[yuxiangdev]

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

}

[mayloveless]

思路

并查集

代码

/**
 * @param {number[][]} isConnected
 * @return {number}
 */
var findCircleNum = function(isConnected) {
    const n = isConnected.length;
    const parent = new Array(n);
    for (let i = 0; i < parent.length; i++) {
       parent[i] = -1;
    }

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

    var count = 0;
    for (let i = 0; i < parent.length; i++) {
        // 统计独立省份
        if (parent[i] == -1) {
            count++;
        }
    }
    return count;
};
function find(parent, i) {
    if (parent[i] == -1) {
        return i;
    }
    return find(parent, parent[i]);
}

function union(parent, x, y) {
    const xset = find(parent, x);
    const yset = find(parent, y);
    if (xset != yset) {
        parent[xset] = yset;// x指向y
    }
}

复杂度

时间O（logn*N^2） 空间O（n）

[Elsa-zhang]

# 547. 省份数量
class Solution:
    def findCircleNum(self, isConnected: list[list[int]]):
        def find(index):
            if parent[index]!=index:
                parent[index] = find(parent[index])
            return parent[index]

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

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

        for i in range(num_city):
            for j in range(i+1, num_city):
                if isConnected[i][j] == 1:
                    union(i,j) 
        print(parent)
        return  sum([parent[i]==i for i in range(num_city)])

isConnected = [[1,1,0],[1,1,0],[0,0,1]]
s = Solution()
ans = s.findCircleNum(isConnected)
print(ans)

[tiandao043]

思路

并查集

代码

class Solution {
public:
    int find(vector<int>& parent,int i){
        if(parent[i]==-1)return i;
        return find(parent,parent[i]);
    }
    void unio(vector<int>& parent,int x,int y){
        int xset=find(parent,x);
        int yset=find(parent,y);
        if(xset!=yset)parent[xset]=yset;
    }
    int findCircleNum(vector<vector<int>>& M) {
        int n=M.size();
        vector<int> parent(n,-1);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(M[i][j]==1&&i!=j){
                    unio(parent,i,j);
                }
            }
        }
        int count=0;
        for(int i=0;i<n;i++){
            if(parent[i]==-1){
                count++;
            }
        }
        return count;
    }
};

时间复杂度 O(n^2logn)，其中 n 是城市的数量。需要遍历矩阵 isConnected 中的所有元素，时间复杂度是 O(n^2)，如果遇到相连关系，则需要进行 2 次查找和最多 1 次合并，一共需要进行 2n^2次查找和最多 n^2次合并，因此总时间复杂度是 O(n^2 log n)。这里的并查集使用了路径压缩，但是没有使用按秩合并，最坏情况下的时间复杂度是 O(n^2log n)，平均情况下的时间复杂度依然是 O(n^2 α(n))，其中 α 为阿克曼函数的反函数，α(n) 可以认为是一个很小的常数。 空间复杂度 O(n)

[klspta]

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

[paopaohua]

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++){
            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]){
                visited[j] = true;
                dfs(isConnected, visited, j);
            }
        }
    }

[whoam-challenge]

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

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

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

    return provinces

[Jetery]

思路

使用并查集, 初始有n个, 每连接两个没有连接的, ans--

code

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

[RestlessBreeze]

code

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