发广播 --- 华为od刷题

题目描述

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

给定一个N*N的二维数组matrix,数组的元素都是字符’0’或者’1’。

matrix[i][j] = ‘1’, 代表i和j站点之间有连接，

matrix[i][j] = ‘0’, 代表没连接，

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

输入描述

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

比如：110,110,001。

输出描述

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

用例

参考

【华为OD机试 】 发广播（C++ Java JavaScript Python）

C++

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


class UnionFindSet {
public:
    vector<int> parent; // parent数组保存每个节点的父节点
    int count; // 连通分量的个数

    UnionFindSet(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) parent[i] = i; // 初始化每个节点的父节点为自己
        count = n; // 初始时有n个连通分量
    }

    int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]); // 路径压缩，将x到根节点路径上的所有节点的父节点都指向根节点
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int root_x = find(x);
        int root_y = find(y);

        if (root_x != root_y) {
            parent[root_y] = root_x; // 将root_y的父节点指向root_x，合并两个连通分量
            count--; // 连通分量个数减一
        }
    }
};

int main() {
    string input;
    getline(cin, input);

    vector<string> matrix;
    string temp = "";
    for (char c : input) {
        if (c == ',') {
            matrix.push_back(temp);
            temp = "";
        }
        else {
            temp += c;
        }
    }
    matrix.push_back(temp);
    int n = matrix.size();

    UnionFindSet ufs(n);

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (matrix[i][j] == '1') {
                ufs.unite(i, j);
            }
        }
    }
    cout << ufs.count << endl; // 输出连通分量个数

    return 0;
}