528
个编辑
更改
跳到导航
跳到搜索
建立内容为“Category:刷题 并查集：用于处理一些不交集（Disjoint sets）的合并及查询问题。 == 算法 == === 添加 === 新添加一个元素时…”的新页面
[[Category:刷题]]
并查集：用于处理一些不交集（Disjoint sets）的合并及查询问题。
== 算法 ==
=== 添加 ===
新添加一个元素时，它的 parent 是它自己。
=== 查询 ===
每个集合的代表是集合的根节点。在查询时进行路径压缩。
<syntaxhighlight lang=python>
def find_representative(x):
if x.parent == x:
return x
else:
x.parent = find_representative(x.parent)
return x.parent
</syntaxhighlight>
=== 合并 ===
{{TODO|union}}
== 相关题目 ==
=== [https://leetcode.com/problems/number-of-provinces/ LeetCode 547. Number of Provinces] ===
Python 解法：
<syntaxhighlight lang=python>
def findCircleNum(self, isConnected: List[List[int]]) -> int:
'''
Union Find solution. Begins by seting the number of provinces to the
number of cities, then union each pair of the connected cities. If they
belong to different sets before the union, reduce the number of
provinces by 1 (unioned two cities into one province).
'''
city_num = len(isConnected)
representative = [i for i in range(city_num)]
def find_repr(c):
if representative[c] == c:
return c
else:
representative[c] = find_repr(representative[c])
return representative[c]
ret = city_num
for i in range(city_num):
for j in range(i + 1, city_num):
if not isConnected[i][j]:
continue
if (ri := find_repr(i)) != (rj := find_repr(j)):
# Connected cities are in different sets. Union them and
# reduce the number of provinces
representative[ri] = rj
ret -= 1
return ret
</syntaxhighlight>
== 另见 ==
* [[wikipedia:Disjoint-set_data_structure]]
并查集：用于处理一些不交集（Disjoint sets）的合并及查询问题。
== 算法 ==
=== 添加 ===
新添加一个元素时，它的 parent 是它自己。
=== 查询 ===
每个集合的代表是集合的根节点。在查询时进行路径压缩。
<syntaxhighlight lang=python>
def find_representative(x):
if x.parent == x:
return x
else:
x.parent = find_representative(x.parent)
return x.parent
</syntaxhighlight>
=== 合并 ===
{{TODO|union}}
== 相关题目 ==
=== [https://leetcode.com/problems/number-of-provinces/ LeetCode 547. Number of Provinces] ===
Python 解法：
<syntaxhighlight lang=python>
def findCircleNum(self, isConnected: List[List[int]]) -> int:
'''
Union Find solution. Begins by seting the number of provinces to the
number of cities, then union each pair of the connected cities. If they
belong to different sets before the union, reduce the number of
provinces by 1 (unioned two cities into one province).
'''
city_num = len(isConnected)
representative = [i for i in range(city_num)]
def find_repr(c):
if representative[c] == c:
return c
else:
representative[c] = find_repr(representative[c])
return representative[c]
ret = city_num
for i in range(city_num):
for j in range(i + 1, city_num):
if not isConnected[i][j]:
continue
if (ri := find_repr(i)) != (rj := find_repr(j)):
# Connected cities are in different sets. Union them and
# reduce the number of provinces
representative[ri] = rj
ret -= 1
return ret
</syntaxhighlight>
== 另见 ==
* [[wikipedia:Disjoint-set_data_structure]]