【华为OD机试2023】Linux发行版的数量Python
题目描述：
Linux操作系统有多个发行版，distrowatch.com提供了各个发行版的资料。这些发行版互相存在关联，例如Ubuntu基于Debian开发，而Mint又基于Ubuntu开发，那么我们认为Mint同Debian也存在关联。 发行版集是一个或多个相关存在关联的操作系统发行版，集合内不包含没有关联的发行版。 给你一个 n x 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)和Ubuntu(2)相关，Mint(3)和Ubuntu(2)相关，EeulerOS(4)和另外三个都不相关，所以存在两个发行版集，发行版集中发行版的数量分别是3和1，所以输出3
解题思路：
方法很多，我用的是dfs遍历
n=int(input())
isConnected=[list(map(int,input().split())) for i in range(n)]
guanlian=[]
def dfs(isConnected,i):
seen = set()
stack = []
stack.append(i)
seen.add(i)
while stack!=[]:
x=stack.pop()
for j in range(n):
if j!=i and isConnected[i][j]==1 and j not in seen:
stack.append(j)
seen.add(j)
return len(seen)
for i in range(n):
guanlian.append(dfs(isConnected,i))
print(max(guanlian))
类似资料：