发广播

【编程题目 |200分】发广播 【2021 H2, 2022 Q1,Q2 考试题】

[编程 | 300分] 发广播 【2021 春招考试题】

■ 题目描述

• 某地有N个广播站，站点之间有些有连接，有些没有。有连接的站点在接受到广播后会互相发送。
• 给定一个N*N的二维数组matrix,数组的元素都是字符’0’或者’1’。matrix[i][j]=‘1’,则代表i和j站点之间有连接，matrix[i][j] = ‘0’代表没连接，
• 现在要发一条广播，问初始最少给几个广播站发送，才能保证所有的广播站都收到消息。

输入描述：

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

输出描述：

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

示例1   输入输出示例仅供调试，后台判题数据一般不包含示例

输入

110,110,001

输出

2

说明

站点1和站点2直接有连接，站点3和其他的都没连接，所以开始至少需要给两个站点发送广播。

另外一种输入形式

示例1

输入

1 0 0
0 1 0
0 0 1

输出

3

说明

3台服务器互不连接，所以需要分别广播这3台服务器。

示例2

输入

1 1
1 1

输出

1

说明

2台服务器相互连接，所以只需要广播其中一台服务器

代码实现

C++解法一

#include<bits/stdc++.h>

using namespace std;
vector<int> fa(50);

class Solution {
public:
    int find(int x) {
        if (fa[x] != x) fa[x] = find(fa[x]);
        return fa[x];
    }

剩余50%内容，订阅会员后查看

C++解法二

#include<bits/stdc++.h>

using namespace std;

void DFS(vector<vector<int>> &adjs, int i, vector<bool> &visited);

剩余50%内容，订阅会员后查看

C++解法三

#include<bits/stdc++.h>

using namespace std;

剩余50%内容，订阅会员后查看

JAVA

import java.util.*;

public class ServerBroadcast {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String[] s = sc.nextLine().split(" ");

剩余50%内容，订阅会员后查看

Python

data = []
d0 = list(map(int, input().split()))

剩余50%内容，订阅会员后查看

JavaScript

剩余50%内容，订阅会员后查看

STICK永久会员

打赏 收藏 海报 链接