网易互娱第二题
网易互娱第二题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();
}
} 
查看8道真题和解析