AcWing 848. 【Java】有向图的拓扑序列
原题链接
简单
作者:
tt2767
,
2020-03-13 16:34:34
,
所有人可见
,
阅读 1026
/**
1. 记录每个点的入度
2. BFS 时将可到达点的入度 减一, 并将入度为0 的点入队
*/
import java.util.*;
import java.util.stream.*;
class Main{
List<List<Integer>> graph = new ArrayList<>();
int[] in;
void run(){
int n = jin.nextInt();
int m = jin.nextInt();
in = new int[n];
for(int i = 0; i < n ; i++) graph.add(new ArrayList<>());
for (int i = 0 ; i < m ; i++){
int x = jin.nextInt() - 1;
int y = jin.nextInt() - 1;
add(x, y);
}
String res = topSort();
System.out.println(res == null ? "-1": res);
}
void add(int x, int y){
graph.get(x).add(y);
in[y] ++ ;
}
String topSort(){
Queue<Integer> queue = new LinkedList<>();
List<Integer> res = new ArrayList<>();
for (int i = 0 ; i < in.length ; i++){
if (in[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()){
int x = queue.poll();
res.add(x);
List<Integer> edges = graph.get(x);
for (int j = 0 ; j < edges.size(); j ++){
int p = edges.get(j);
if (--in[p] == 0) queue.offer(p);
}
}
if (res.size() != in.length) return null;
return res.stream().map(x->String.valueOf(x+1)).collect(Collectors.joining(" "));
}
private Scanner jin = new Scanner(System.in);
public static void main(String[] args) {new Main().run();}
}
import java.util.*;
public class Main
{
static int N = 100010;
static int[] in = new int[N];
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int n = 0;
static int idx = 0;
static List[HTML_REMOVED] q = new LinkedList<>();
}
大佬可以帮忙看下我这个代码有什么问题吗?