2022.7.23-----leetcode.剑指offer.115

    int V;//顶点数量
    Deque<Integer>[] adj;//邻接表
    int[] in;//存储每个顶点的入度
    //添加一条边
    public void addEdge(int v,int w){
        if(!adj[v].contains(w)){
            adj[v].offer(w);
            in[w]++;
        }
    }

     public boolean sequenceReconstruction(int[] nums, int[][] ss) {
         V = nums.length;
         in=new int[V+1];
        adj = new ArrayDeque[V+1];
        for (int i = 0; i < adj.length; i++) {
            adj[i]=new ArrayDeque<>();
        }
        //建图
        for(int[] s:ss){
            if(s.length==1)
                continue;
            for(int i=1;i<s.length;i++)
                addEdge(s[i-1],s[i]);
        }
        return topologicalSort1();

     }
     public boolean topologicalSort1(){
        Deque<Integer> q=new ArrayDeque<>();
        //将入度为0的顶点加入队列
        for (int i = 1; i <= V; i++) {
            if(in[i]==0)
                q.add(i);
        }
        //如果nums唯一，每次q中只能有一个顶点
        if(q.size()>1)
            return false;
        while(!q.isEmpty()){
            int v=q.poll();//取出入度为0的顶点
            for (int w:adj[v]) {
                in[w]--;//v指向的顶点入度减1
                if(in[w]==0)
                    q.add(w);
            }
            if(q.size()>1)
                return false;
        }
        return true;//如果能确定包含[1,n]的唯一的序列，必为最短
    }