【算法题】服务器广播

  • A+
所属分类:编程茶楼


共计 1455 个字符,预计需要花费 4 分钟才能阅读完成。

服务器连接方式包括直接连接,间接连接。A和B直接连接,B和C直接连接,则A和C间接连接。直接连接和间接连接都可以发送广播。
给出一个NN数组,代表N个服务器,matrix[i][j] == 1,则代表i和j直接连接;不等于1时,代表i和j不直接连接。matrix[i][i] == 1,即自己和自己直接连接。matrix[i][j] == matrix[j][i]。
计算初始需要给几台服务器广播,才可以使每个服务器都收到广播。

输入描述:
输入为N行,每行有N个数字,为0或1,由空格分隔,构成N*N的数组,N的范围为 1<=N<=40
输出描述:
输出一个数字,为需要广播的服务器的数量

示例1

输入
1 0 0
0 1 0
0 0 1
输出
3
说明
3台服务器互不连接,所以需要分别广播这3台服务器

示例2

输入
1 1
1 1
输出
1
说明
2台服务器相互连接,所以只需要广播其中一台服务器

import java.util.*;

/**
 * @since 2022年4月20日
 */
public class ServerBroadcast {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] servers = scanner.nextLine().split(" ");
        int N = servers.length;
        int count = 0;
        int[][] arrServer = new int[N][N];
        for (int i = 0; i < N; i++) {
            arrServer[count][i] = Integer.parseInt(servers[i]);
        }
        while (++count < N) {
            servers = scanner.nextLine().split(" ");
            for (int i = 0; i < N; i++) {
                arrServer[count][i] = Integer.parseInt(servers[i]);
            }
        }

        // 打印一下二维数组
//        System.out.println(Arrays.deepToString(arrServer));

        Map<Integer, Set<Integer>> map = new HashMap<>();
        //把直接相连的服务器存储起来
        for (int i = 0; i < N; i++) {
            Set<Integer> set = new HashSet<>();
            for (int j = 0; j < N; j++) {
                boolean isSame = arrServer[i][j] == 1;
                if (isSame) {
                    set.add(j);
                    map.put(i, set);
                }
            }
        }
        //取出间接相连的
        for (Map.Entry<Integer, Set<Integer>> entry : map.entrySet()) {
            int key = entry.getKey();
            Set<Integer> broadcastSet = entry.getValue();
            for (Integer broadcast : broadcastSet) {
                if (key != broadcast) {
                    map.put(broadcast, broadcastSet);
                }
            }
        }

        Set<Set<Integer>> ret = new HashSet<>();
        for (Map.Entry<Integer, Set<Integer>> entry : map.entrySet()) {
            ret.add(entry.getValue());
        }
        System.out.println(ret.size());
    }
}
  • 我的微信
  • 这是我的微信扫一扫
  • weinxin
  • 我的微信公众号
  • 我的微信公众号扫一扫
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: