跳至主要內容

剑指 Offer II 116. 省份数量

ITCharge大约 1 分钟

剑指 Offer II 116. 省份数量open in new window

  • 标签:深度优先搜索、广度优先搜索、并查集、图
  • 难度:中等

题目链接

题目大意

一个班上有 n 个同学,其中一些彼此是朋友,另一些不是。如果 ab 是直接朋友,且 bc 也是直接朋友,那么 ac 是间接朋友。

现在定义「朋友圈」是由一组直接或间接朋友组成的集合。

现在给定一个 n * n 的矩阵 isConnected 表示班上的朋友关系。其中 isConnected[i][j] = 1 表示第 i 个同学和第 j 个同学是直接朋友,isConnected[i][j] = 0 表示第 i 个同学和第 j 个同学不是直接朋友。

要求:根据给定的同学关系,返回「朋友圈」的数量。

解题思路

可以利用并查集来做。具体做法如下:

遍历矩阵 isConnected。如果 isConnected[i][j] = 1,将 i 节点和 j 节点相连。然后判断每个同学节点的根节点,然后统计不重复的根节点有多少个,即为「朋友圈」的数量。

代码

class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.count = n

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return

        self.parent[root_x] = root_y
        self.count -= 1

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

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

        return union_find.count