题目描述
Linux操作系统有多个发行版,distrowatch.com提供了各个发行版的资料。这些发行版互相存在关联,例如Ubuntu基于Debian开发,而Mint又基于Ubuntu开发,那么我们认为Mint同Debian也存在关联。
发行版集是一个或多个相关存在关联的操作系统发行版,集合内不包含没有关联的发行版。
给你一个 n * n 的矩阵 isConnected,其中 isConnected[i][j] = 1 表示第 i 个发行版和第 j 个发行版直接关联,而 isConnected[i][j] = 0 表示二者不直接相连。
返回最大的发行版集中发行版的数量。
输入描述
第一行输入发行版的总数量N,
之后每行表示各发行版间是否直接相关
输出描述
输出最大的发行版集中发行版的数量
备注
1 ≤ N ≤ 200
用例1
输入
4
1 1 0 0
1 1 1 0
0 1 1 0
0 0 0 1
输出
3
说明
Debian(1)和Unbuntu2)相关
Mint(3)和Ubuntu(2)相关,
EeulerOS(4)和另外三个都不相关,
所以存在两个发行版集,发行版集中发行版的数量分别是3和1,所以输出3。
class UnionFindSet:
def __init__(self, n):
# 初始化并查集,每个结点自成一个集合,代表自身
self.fa = [idx for idx in range(n)] # 初始化父节点,每个节点的父节点最初设为自身
def find(self, x):
# 查找操作,递归寻找x的根节点,并压缩路径
if x != self.fa[x]:
self.fa[x] = self.find(self.fa[x]) # 压缩路径,直接指向根节点
return self.fa[x] # 返回根节点
return x # 返回自身,代表根节点
def union(self, x, y):
# 合并操作,将x的根节点指向y的根节点
# 找到x和y的根节点
x_fa = self.find(x)
y_fa = self.find(y)
if x_fa != y_fa:
self.fa[y_fa] = x_fa # 将y的根节点指向x的根节点
if __name__ == '__main__':
n = int(input()) # 输入结点数量n
matrix = []
# 输入n行n列的矩阵,表示结点之间的连接关系
for i in range(n):
matrix.append(list(map(int, input().split())))
ufs = UnionFindSet(n) # 创建并查集对象
# 遍历矩阵,如果两个结点有连接关系,则合并它们
for i in range(n):
for j in range(i + 1, n):
if matrix[i][j] == 1:
ufs.union(i, j) # 将有连接关系的结点进行合并
connected = {} # 记录每个集合的大小
for i in range(n):
fa = ufs.find(ufs.fa[i]) # 找到i所在集合的根节点
connected[fa] = connected.get(fa, 0) + 1 # 计算集合的大小
# 输出最大集合的大小
print(max(connected.values()))
标签:__,self,查集,find,---,fa,发行版,Linux,节点
From: https://blog.csdn.net/TTz012/article/details/143439658