题目描述

服务器连接方式包括直接相连，间接连接。
A和B直接连接，B和C直接连接，则A和C间接连接。
直接连接和间接连接都可以发送广播。
给出一个N*N数组，代表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 0 0
0 1 0
0 0 1
输出
3
说明
3 台服务器互不连接，所以需要分别广播这 3 台服务器

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

代码实现

import java.util.*;
import java.util.stream.Collectors;

public class Test {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<List<Integer>> list = new ArrayList<>();
        String s = scanner.nextLine();
        String[] strings = s.split(" ");
        List<Integer> collect = Arrays.stream(strings).map(Integer::valueOf).collect(Collectors.toList());
        list.add(collect);
        int num = collect.size();

        //将数据转换成二维数组
        for (int i = 0; i < num-1; i++) {
            s = scanner.nextLine();
            strings = s.split(" ");
            collect = Arrays.stream(strings).map(Integer::valueOf).collect(Collectors.toList());
            list.add(collect);
        }

        //存放要联通的机器，set中存放该机器可联通的机器编号
        List<Set<Integer>> res = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            boolean flag = false;
            Set<Integer> set = null;
            for (int j = 0; j < res.size(); j++) {
                set = res.get(j);
                if (set.contains(i)){
                    //如果集合中包含当前机器编号，标识该机器没有联通，则跳出循环
                    flag = true;
                    break;
                }
            }

            if (!flag){
                //将该机器的编号加入集合中
                set = new HashSet<>();
                set.add(i);
                res.add(set);
            }
            for (int j = 0; j < num; j++) {
                if (list.get(i).get(j)==1){
                    //将该机器可联通的机器编号加入集合中
                    set.add(j);
                }
            }
        }
        System.out.println(res.size());
    }

}