京东笔试(2018.09.09)第一题:完全多部图

题目截图来自牛客网:

这个题的难度一般,感觉就是编程有点小绕,代码来自llw。从代码中学习到怎么输入一个图的邻接矩阵。这个解决了自己的一个知识盲点

 

public class FirstProblem {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int times = scanner.nextInt();
        for(int i = 0; i < times; ++i){
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            int[][] graph = new int[n][n];
            for(int j = 0; j < m; ++j){
                int start = scanner.nextInt();
                int end = scanner.nextInt();
                graph[start-1][end-1] = 1;
                graph[end-1][start - 1] = 1;
            }
            boolean result = getResult(graph);
            if(result)System.out.println("Yes");
            else System.out.println("No");
        }


    }

    private static boolean getResult(int[][] graph) {
        // map存放的是每一个节点的编号以及与其相邻的节点
        HashMap<Integer, Set<Integer>> map = new HashMap<>();
        HashSet<Integer> allPointHashSet = new HashSet<>();

        // 遍历每一个节点
        for(int i = 0; i < graph.length; ++i){
            allPointHashSet.add(i);
            HashSet<Integer> set = new HashSet<>();
            for(int j = 0; j <graph[i].length; ++j){
                if(graph[i][j] == 1){
                    set.add(j);
                }
            }
            map.put(i,set);
        }

        for(int i = 0; i < graph.length; ++i){
            if(allPointHashSet.contains(i)){
                Iterator<Integer> iterator = allPointHashSet.iterator();
                HashSet<Integer> one = new HashSet<>(map.get(i));
                HashSet<Integer> another = new HashSet<>();
                another.add(i);
                while(iterator.hasNext()){
                    Integer j = iterator.next();
                    if(i != j && !map.get(i).contains(j)){
                        another.add(j);
                        one.retainAll(map.get(j));
                    }
                }
                Iterator<Integer> integerIterator = another.iterator();
                while (integerIterator.hasNext()) {
                    System.out.print(integerIterator.next()+"\t");
                }
                System.out.println();
                if(another.size() + one.size() != graph.length){
                    return false;
                }
            }
        }

        return true;
    }
}

 

说点什么

avatar
  Subscribe  
提醒

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部