刷题笔记合集🔗

发广播

问题描述

某地有 个广播站，站点之间有些有连接，有些没有。有连接的站点在接受到广播后会互相发送。

给定一个 的二维数组 ，数组的元素都是字符'0'或者'1'。

，代表 和 站点之间有连接，

，代表没连接，

现在要发一条广播，问初始最少给几个广播站发送，才能保证所有的广播站都收到消息。

输入格式

从 stdin 输入，共一行数据，表示二维数组的各行，用逗号分隔行。保证每行字符串所含的字符数一样的。

比如：110,110,001。

输出格式

返回初始最少需要发送广播站个数。

样例输入

110,110,001

100,010,001

11,11

样例输出

2

3

1

数据范围

样例	解释说明
样例1	站点1和站点2直接有连接，站点3和其他的都没连接，所以开始至少需要给两个站点发送广播。
样例2	3台服务器互不连接，所以需要分别广播这3台服务器。
样例3	2台服务器相互连接，所以只需要广播其中一台服务器。

题解

这道题本质上是要求图中的连通分量的数量。由于有连接的站点可以互相发送广播，所以一个连通分量内只需要给一个站点发送广播，整个连通分量内的所有站点就都能收到消息。因此，最少需要发送的广播站数量就等于图中连通分量的数量。

解题思路可以使用并查集（Union-Find Set）数据结构，这是一种非常适合处理图的连通性问题的工具。

首先，我们需要认识到，矩阵 表示的是一个无向图，如果 ，则表示站点 和站点 之间有连接。矩阵应该是对称的，即 。

解题步骤如下：

1. 初始化并查集，一开始每个站点都是独立的，连通分量数量等于站点总数
2. 遍历矩阵的上三角部分（因为矩阵是对称的），当 时，将站点 和站点 合并到同一个连通分量中
3. 每次合并操作如果成功（即两个站点原本不在同一个连通分量中），则连通分量数量减1
4. 最终，连通分量的数量就是需要发送广播的最小站点数

并查集的关键操作：

• find：查找一个站点所属的连通分量（即查找其根节点）
• union：合并两个连通分量

这个算法的时间复杂度是 ，其中 是阿克曼函数的反函数，实际应用中可以视为常数。 是遍历矩阵的复杂度。

使用并查集解决这个问题是高效的，尤其是对于大规模的图。代码实现简洁，且具有很好的可读性和可维护性。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 输入获取
matrix = input().split(",")

# 并查集实现
class UFSet:
    def __init__(self, n):
        # 初始化，每个节点的父节点是自己
        self.par = [i for i in range(n)]
        # 初始连通分量数量为n
        self.cnt = n
    
    def find(self, x):
        # 路径压缩查找，优化查找效率
        if x != self.par[x]:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        return x
    
    def merge(self, x, y):
        # 合并两个节点所在的连通分量
        rx = self.find(x)
        ry = self.find(y)
        
        # 如果两个节点不在同一连通分量中，则合并
        if rx != ry:
            self.par[ry] = rx
            # 连通分量数量减1
            self.cnt -= 1

def solve(grid):
    n = len(grid)
    
    # 创建并查集
    uf = UFSet(n)
    
    # 遍历矩阵上三角部分
    for i in range(n):
        for j in range(i+1, n):
            # 如果两个站点之间有连接，则合并
            if grid[i][j] == "1":
                uf.merge(i, j)
    
    # 返回连通分量数量
    return uf.cnt

# 调用函数并输出结果
print(solve(matrix))

• Cpp

#include <bits/stdc++.h>
using namespace std;

// 并查集实现
class DisjointSet {
private:
    vector<int> root;  // 存储每个节点的父节点
    int count;         // 连通分量数量

public:
    // 构造函数，初始化并查集
    DisjointSet(int n) {
        root.resize(n);