题目描述与示例

题目描述

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

示例一

输入

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

解题思路

本题用关联矩阵的形式表示图，类似于LC547.省份数量，但在设问上是求最大发行版集的数量，类似于LC695. 岛屿的最大面积，所以我们只需要将两题结合并稍作修改即可完成本题。

代码

解法一：BFS

# BFS
from collections import deque

n = int(input())
isConnected = list()
for _ in range(n):
    isConnected.append(list(map(int, input().split())))

ans = 0
checkList = [0] * n     # 构建检查数组checkList

# 遍历每一个版本
for i in range(n):
    if checkList[i] == 0:       # 若版本i未检查过
        q = deque([i])          # 把版本i加入q中，作为BFS的起始位置
        checkList[i] = 1        # 将版本i标记为已检查过
        cur_num = 0             # cur_num表示本次BFS包含的版本数，初始化为0
        # 从版本i开始，进行BFS
        while(q):
            # 弹出q队头的版本x，考虑所有与其相连的版本y
            x = q.popleft()
            # 本次搜索得到的版本数目+1
            cur_num += 1
            # 对于版本x，遍历所有其他版本y，若y未检查过，且与x相连
            for y in range(n):
                if x != y and checkList[y] == 0 and isConnected[x][y] == 1:
                    q.append(y)         # 则把版本y加入队列中
                    checkList[y] = 1    # 同时把版本y标记为已检查过
        # 完成本次BFS，比较ans和cur_num，更新ans
        ans = max(ans, cur_num)

print(ans)

解法二：DFS

# DFS
def dfs(x, isConnected, checkList):
    # 声明变量cur_num为全局变量，表示当前DFS所遍历的版本数
    global cur_num
    cur_num += 1
    # 对于传入的版本x，将其标记为已检查过
    checkList[x] = 1
    # 遍历其他版本y，若版本y未检查过，且与版本x相连
    for y in range(n):
        if y != x and checkList[y] == 0 and isConnected[x][y] == 1:
            dfs(y, isConnected, checkList)  # 则对y进行DFS

n = int(input())
isConnected = list()
for _ in range(n):
    isConnected.append(list(map(int, input().split())))

ans = 0
checkList = [0] * n         # 构建检查数组checkList

# 遍历每一个版本
for i in range(n):
    # 如果该版本没检查过，则以版本i作为起始点，进行DFS
    if checkList[i] == 0:
        # cur_num表示本次DFS包含的版本数，初始化为0
        cur_num = 0
        # 进行DFS搜索
        dfs(i, isConnected, checkList)
        # 完成本次BFS，比较ans和cur_num，更新ans
        ans = max(ans, cur_num)

print(ans)

时空复杂度

时间复杂度：O(N^2)。需要遍历整个关联矩阵 isConnected。

空间复杂度：O(N)。