广播服务器 - 华为OD机试2022

题目描述

解题思路

思路：本质是图的遍历, 计算多少个连通图。

1. 初始化一个邻接表，key和value相等，数量是所有的行数（方阵）
2. 遍历所有的位置， (当前点是0也不考虑，i==j这种情况是自己和自己相连不考虑。) 考虑的是当前点是1and i!=j, 后者表示两个不同的点相连。如果这两个点在tag中的标号也就是value相同，表示连通，不作任何操作，如果不同，表示不连通，需要将两者连通起来，也就是使两者的value相等，大的标号向小的标号对齐。（之前看最小生成树就是这样做的，小的标号向大的标号看齐就会错误，不知道为啥。）
3. 最后把value做个集合，求个数就可以了。

python代码

'''
思路：本质是图的遍历, 计算多少个连通图
这个题借鉴了最小生成树中的回路判断: https://www.nowcoder.com/discuss/466406145142300672?sourceSSR=users

'''
def cal(matrix):
    # 矩阵是方阵
    # 邻接表初始化, 遍历方阵, 如果联通就大的标号向小的标号看齐。
    n = len(matrix)
    tag = {i:i for i in range(n)} # {0: 0, 1: 0, 2: 2}
    for i in range(n):
        for j in range(n):
            if matrix[i][j] == 1 and i != j:
                if tag[i] != tag[j]:
                    # 把边对应的两个节点对应的编号置为相同，大的向小的看齐。
                    max_v = max(tag[i], tag[j]) # 找顶点标号大的
                    min_v = min(tag[i], tag[j]) # 找顶点标号小的
                    for i in range(n):  # 找所有的顶点
                        if tag[i] == max_v: # 顶点对应的标号等于大的那个
                            tag[i] = min_v  # 大的标号向小的标号看齐

    print(tag)  
    # value相同的视为一个联通图，计算多少个不同的value 就是多少个连通图
    num = len(set(tag.values()))
    return num

# matrix= [[1,1,0],[1,1,0],[0,0,1]]
# matrix= [[1,0,0],[0,1,0],[0,0,1]]
# matrix= [[1,1],[1,1]]
matrix= [[1,1,0,0],[1,1,0,1],[0,0,1,1],[0,1,1,1]]  # 1
print(cal(matrix))