网易互娱第二题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) 回帖