牛客NC314 体育课测验(一)【中等 图,BFS,拓扑排序 Java,Go、PHP】-参考答案Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param numProject int整型 
     * @param groups int整型ArrayList<ArrayList<>> 
     * @return bool布尔型
     */
    public boolean canFinish (int numProject, ArrayList<ArrayList<Integer>> groups) {
          //图,bfs,拓扑排序
            Map<Integer,GNode> graph = new HashMap<>();
            for (int i = 0; i <numProject ; i++) {
                graph.put(i,new GNode(i));
            }

            for (ArrayList<Integer> group : groups) {
                int vf = group.get(1);
                int tf = group.get(0);

                GNode fn = graph.get(vf);
                GNode tn = graph.get(tf);
                fn.nexts.add(tn);
                tn.in++;
            }


            Queue<GNode> q0 = new LinkedList<>();
            Set<Integer> visited = new HashSet<>();
            for(int k: graph.keySet()){
                if(graph.get(k).in==0){
                    q0.add(graph.get(k));
                    visited.add(graph.get(k).data);
                }
            }


            List<Integer> ll = new ArrayList<>();
            while (!q0.isEmpty()){
                int size = q0.size();
                for (int i = 0; i <size ; i++) {
                    GNode pop = q0.poll();
                    ll.add(pop.data);
                    for (GNode next : pop.nexts) {
                        if(--next.in==0){
                            if(visited.contains(next.data)) return false; //出现环了
                            q0.add(next);
                            visited.add(next.data);
                        }
                    }
                }
            }

            return ll.size()  == numProject? true: false;
        }

        static class GNode{
            int data;
            int in;
            List<GNode> nexts;
            public GNode(int d){
                data =d;
                in =0;
                nexts = new ArrayList<>();
            }
        }
}
上一篇:python 面向对象


下一篇:146.LRU缓存