首页 > 网易互娱第二题
头像
牛客566012114号
发布于 2021-08-07 22:51
+ 关注

网易互娱第二题

网易互娱第二题50%之后超时,实在没搞懂我为什么超时,半个小时写出来,改了一个小时还超时
思路就是拓扑排序
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        String[] strings = new String[t];
        for(int y=0;y<t;y++){
            int n = in.nextInt();
            int m = in.nextInt();
            strings[y]= iscan(n, m, in);
        }
        for (String string : strings) {
            System.out.println(string);
        }
    }

    public static String iscan(int n, int m, Scanner in){
        HashMap<Integer, Set<Integer>> map = new HashMap<>();
        int[] cns = new int[n];
        for(int i=0;i<n;i++){
            Set<Integer>set = new HashSet<>();
            map.put(i+1,set);
        }
        for(int i=0;i<m;i++) {
            int k = in.nextInt();
            int[] re = new int[k];
            for (int j = 0; j < k; j++)
                re[j] = in.nextInt();
            for (int j = 0; j < k-1; j++) {
                if(!map.get(re[j]).contains(re[j+1])){
                    cns[re[j+1]-1]++;
                    map.get(re[j]).add(re[j+1]);
                }
            }
        }
        Queue<Integer> queue = new ArrayDeque<>();
        StringBuilder builder = new StringBuilder();
        for(int i=0;i<n;i++){
            if(cns[i]==0){
                queue.add(i+1);
            }
        }
        int count =0;
        while (!queue.isEmpty()){
            count++;
            if(queue.size()>1) return "NO";
            int now = queue.poll();
            if(count<n)
                builder.append(now + " ");
            else builder.append(now);
            for (Integer integer : map.get(now)) {
                cns[integer-1]--;
                if(cns[integer-1]==0)
                    queue.add(integer);
            }
        }
        //System.out.println(builder.toString().strip());
        return builder.toString();
    }
}


全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐