class UnionFind:
def __init__(self, n: int):
# 一开始有 n 个集合 {0}, {1}, ..., {n-1}
# 集合 i 的代表元是自己
self._fa = list(range(n)) # 代表元
self.cc = n # 连通块个数
# 返回 x 所在集合的代表元
# 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
def find(self, x: int) -> int:
# 如果 fa[x] == x，则表示 x 是代表元
if self._fa[x] != x:
self._fa[x] = self.find(self._fa[x]) # fa 改成代表元
return self._fa[x]
# 把 from 所在集合合并到 to 所在集合中
def merge(self, from_: int, to: int) -> None:
x, y = self.find(from_), self.find(to)
if x == y: # from 和 to 在同一个集合，不做合并
return
self._fa[x] = y # 合并集合。修改后就可以认为 from 和 to 在同一个集合了
self.cc -= 1 # 合并后，连通块个数减少了 1
class Solution:
def numberOfComponents(self, properties: List[List[int]], k: int) -> int:
sets = list(map(set, properties))
uf = UnionFind(len(properties))
for i, a in enumerate(sets):
for j, b in enumerate(sets[:i]):
if len(a & b) >= k:
uf.merge(j, i)
return uf.cc
class UnionFind:
def __init__(self, n: int):
# 一开始有 n 个集合 {0}, {1}, ..., {n-1}
# 集合 i 的代表元是自己
self._fa = list(range(n)) # 代表元
self.cc = n # 连通块个数
# 返回 x 所在集合的代表元
# 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
def find(self, x: int) -> int:
# 如果 fa[x] == x，则表示 x 是代表元
if self._fa[x] != x:
self._fa[x] = self.find(self._fa[x]) # fa 改成代表元
return self._fa[x]
# 把 from 所在集合合并到 to 所在集合中
def merge(self, from_: int, to: int) -> None:
x, y = self.find(from_), self.find(to)
if x == y: # from 和 to 在同一个集合，不做合并
return
self._fa[x] = y # 合并集合。修改后就可以认为 from 和 to 在同一个集合了
self.cc -= 1 # 合并后，连通块个数减少了 1
class Solution:
def numberOfComponents(self, properties: List[List[int]], k: int) -> int:
sets = [reduce(or_, (1 << x for x in a)) for a in properties]
uf = UnionFind(len(properties))
for i, a in enumerate(sets):
for j, b in enumerate(sets[:i]):
if (a & b).bit_count() >= k:
uf.merge(j, i)
return uf.cc
class UnionFind {
private final int[] fa;
public int cc; // 连通块个数
UnionFind(int n) {
fa = new int[n];
cc = n;
for (int i = 0; i < n; i++) {
fa[i] = i;
}
}
public int find(int x) {
if (fa[x] != x) {
fa[x] = find(fa[x]);
}
return fa[x];
}
public void merge(int from, int to) {
int x = find(from);
int y = find(to);
if (x == y) {
return;
}
fa[x] = y;
cc--;
}
}
class Solution {
public int numberOfComponents(int[][] properties, int k) {
int n = properties.length;
int m = properties[0].length;
Set<Integer>[] sets = new HashSet[n];
Arrays.setAll(sets, i -> new HashSet<>(m));
for (int i = 0; i < n; i++) {
for (int x : properties[i]) {
sets[i].add(x);
}
}
UnionFind u = new UnionFind(n);
for (int i = 0; i < n; i++) {
Set<Integer> a = sets[i];
for (int j = 0; j < i; j++) {
int cnt = 0;
for (int x : sets[j]) {
if (a.contains(x)) {
cnt++;
}
}
if (cnt >= k) {
u.merge(i, j);
}
}
}
return u.cc;
}
}
type uf struct {
fa []int
cc int
}
func newUnionFind(n int) uf {
fa := make([]int, n)
for i := range fa {
fa[i] = i
}
return uf{fa, n}
}
func (u uf) find(x int) int {
if u.fa[x] != x {
u.fa[x] = u.find(u.fa[x])
}
return u.fa[x]
}
func (u *uf) merge(from, to int) {
x, y := u.find(from), u.find(to)
if x == y {
return
}
u.fa[x] = y
u.cc--
}
func numberOfComponents(properties [][]int, k int) int {
sets := make([]map[int]bool, len(properties))
for i, a := range properties {
sets[i] = map[int]bool{}
for _, x := range a {
sets[i][x] = true
}
}
u := newUnionFind(len(properties))
for i, a := range sets {
for j, b := range sets[:i] {
cnt := 0
for x := range b {
if a[x] {
cnt++
}
}
if cnt >= k {
u.merge(i, j)
}
}
}
return u.cc
}
