服务器广播

• 服务器连接方式包括直接相连，间接连接。
• 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] 。
• 计算初始需要给几台服务器广播，才可以使每个服务器都收到广播。

import java.util.*;
public class Question43 {
    public static void main(String[] args) {
	  //测试用例
        int[][] arr = new int[][]{{1,0,1,0,1,1},{0,1,0,0,0,0},{1,0,1,0,0,0},{0,0,0,1,0,0},{1,0,0,0,1,0},{1,0,0,0,0,1}};
	  //如果answer方法中不加while循环，此用例的输出结果是2，显然是错误的，加上while循环，结果为1；
	  //int[][] arr = new int[][]{{1,1,0,0,0},{0,1,1,0,0},{0,0,1,1,0},{0,0,0,1,1},{0,0,0,0,1}};

        System.out.println(answer(arr));
    }

    public static int answer(int[][] arr){
	  //存放对应关系的集合，key为服务器，value为能广播到的集合
        Map<Integer, Set<Integer>> resultMap = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                if (arr[i][j] == 1){
                    if (!resultMap.containsKey(i)){
                        Set<Integer> set = new HashSet<>();
                        set.add(j);
                        resultMap.put(i, set);
                    }else {
                        resultMap.get(i).add(j);
                    }
                }
            }
        }
	  //因为A -> B， B -> C 则需要将B的关系同时放到A的关系中，考虑到可能有n层继承关系，设置一个变量值，如果在一次循环中，所有的set的大小都没有发生变化，那么就可以认为，每个广播下的所有直接、间接连接的广播都已经列出，瑞出循环
        while (true) {
            int count = 0;
            for (int i = 0; i < arr.length; i++) {
                if (resultMap.containsKey(i)) {
                    Set<Integer> set = resultMap.get(i);
                    int size = set.size();
                    Set<Integer> temp = new HashSet<>();
                    for (Integer items : set) {
                        Set<Integer> set1 = resultMap.get(items);
                        temp.addAll(set1);
                    }
                    set.addAll(temp);
                    if (size != set.size()){
                        count = 1;
                    }
                }
            }
            if (count == 0){
                break;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            if (resultMap.containsKey(i)){
                Set<Integer> set = resultMap.get(i);
                for (Integer items : set){
                    if (items != i) resultMap.remove(items);
                }
            }
        }
        return resultMap.size();
    }

}