E卷-刷题笔记合集🔗

服务器广播-需要广播的服务器数量

问题描述

某地区有 个广播站，这些站点之间可能存在连接。当两个站点之间有连接时，如果其中一个站点接收到广播，它会自动将广播传递给与之相连的站点。

现给定一个 的二维数组 ，其中的元素只包含字符 '0' 或 '1'：

• 若 ，表示第 个站点和第 个站点之间有连接。
• 若 ，表示第 个站点和第 个站点之间没有连接。

现需要发送一条广播，请计算出最少需要向多少个广播站发送初始信号，才能确保所有广播站都能收到这条广播。

输入格式

输入为一个 的二维数组 ，每行包含 个用空格分隔的字符 '0' 或 '1'。

输出格式

输出一个整数，表示初始最少需要发送广播的站点数量。

样例输入1

1 0 0
0 1 0
0 0 1

样例输出1

3

样例输入2

1 1
1 1

样例输出2

1

样例输入3

1 1 0
1 1 0
0 0 1

样例输出3

2

样例解释

数据范围

题解

并查集

这道题目本质上是在寻找图中的连通分量数量。每个连通分量至少需要一个初始广播站。可以使用并查集（Disjoint Set Union）来解决这个问题。

并查集是一种树形的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。对于这道题：

1. 初始化：每个广播站自成一个集合。
2. 遍历矩阵：当遇到 matrix[i][j] = 1 时，将 i 和 j 所在的集合合并。
3. 最后，统计剩余的集合数量，即为所需的最少初始广播站数。

使用并查集的关键在于它能高效地合并集合和判断元素是否属于同一集合。在这个问题中，能快速找出所有相互连接的广播站群组。

时间复杂度分析：

• 初始化：O(N)
• 遍历矩阵并合并：O(N^2 * α(N))，其中 α(N) 是阿克曼函数的反函数，实际上可以视为常数。
• 统计集合数量：O(N)

参考代码

• Cpp

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class UnionFind {
private:
    vector<int> parent;  // 存储每个节点的父节点
    vector<int> rank;    // 用于优化合并操作的秩
    int count;           // 记录集合的数量

public:
    // 构造函数，初始化并查集
    UnionFind(int n) : parent(n), rank(n, 0), count(n) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // 初始时，每个节点的父节点是自己
        }
    }

    // 查找操作，找到x的根节点
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩
        }
        return parent[x];
    }

    // 合并操作，将x和y所在的集合合并
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;  // 已经在同一集合中

        // 按秩合并
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        count--;  // 合并后，集合数量减1
    }

    // 获取当前集合的数量
    int getCount() const {
        return count;
    }
};

// 计算最少需要的广播站数量
int minBroadcastStations(const vector<vector<char>>& matrix) {
    int n = matrix.size();
    UnionFind uf(n);

    // 遍历矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '1') {
                uf.unite(i, j);  // 如果有连接，则合并
            }
        }
    }

    return uf.getCount();  // 返回剩余的集合数量，即为所需的广播站数量
}

int main() {
    vector<vector<char>> matrix;
    string line;

    // 读取输入
    while (getline(cin, line)) {
        vector<char> row;
        for (char c : line) {
            if (c == '0' || c == '1') {
                row.push_back(c);
            }
        }
        if (!row.empty()) {
            matrix.push_back(row);
        }
    }

    // 计算并输出结果
    int result = minBroadcastStations(matrix);
    cout << result << endl;

    return 0;
}

• Python

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # 初始化每个节点的父节点为自身
        self.rank = [0] * n  # 用于优化合并操作的秩
        self.count = n  # 记录集合的数量

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        self.count -= 1  # 合并后集合数量减1

def min_broadcast_stations(matrix):
    n = len(matrix)
    uf