【Day 76 】2024-06-22 - 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]

[zhiyuanpeng]

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

    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, x, y):
        parent_x = self.find(x)
        parent_y = self.find(y)

        if parent_x != parent_y:
            self.size -= 1
            self.parent[parent_x] = parent_y

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

space O(N), time (N^2)

[CathyShang]

class uk:
    def __init__(self, M):
        self.parent = {}
        self.cnt = 0
        for i in range(M):
            # for j in range(i, n):
            #     if i not in self.parent:
            #         self.parent[i] = []
            self.parent[i]=i #自己是自己的parent
            self.cnt += 1
    def find(self, x):
        while x != self.parent[x]:
            x = self.parent[x]
        return self.parent[x]

    # 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:
            self.cnt -= 1
            self.parent[parent_p] = parent_q
        # if self.connected(p,q):return
        # leader_p = self.find(p)
        # leader_q = self.find(q)
        # self.parent[leader_p] = leader_q
        # self.cnt -= 1

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        unfind = uk(n) # 初始化并查集
        for i in range(n):
            for j in range(i+1,n):
                if isConnected[i][j]: # 仅联通，代表是谁？
                    # tmp = unfind.find(i)
                    # if unfind.find(j)==tmp:
                    #     break
                    unfind.union(i,j)
        return unfind.cnt

[Dtjk]

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

};