题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，给一个二维数组代表一个个点，一个一维数组代表一个点的内容，先规定给定数值 k，任意两个不同的点有超过 k 各相同的各异值则相连，求现在图中的连通分量。

思路分享

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def numberOfComponents(self, properties: List[List[int]], k: int) -> int:
        n = len(properties)
        cc = n
        for i in range(n):
            properties[i] = set(properties[i])
        
        rec = list(range(n+1))
        def find(index:int) -> int:
            if not rec[index] == index:
                rec[index] = find(rec[index])
            return rec[index]
        def merge(i:int, j:int) -> None:
            rec[find(i)] = rec[find(j)]

        for i, p in enumerate(properties):
            for j, q in enumerate(properties):
                if i == j:
                    continue
                if not find(i) == find(j) and len(p & q) >= k:
                    # print(i, j, p, q, p and q)
                    merge(i, j)
                    cc -= 1
        return cc