题目描述
blablabla
样例
import java.util.*;
class Main{
static int idx;
static int[] h, ne, e;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
init(n, m);
int[] inDegrees = new int[n + 1];
for (int i = 0; i < m; i++) {
int a = sc.nextInt(), b = sc.nextInt();
add(a, b);
inDegrees[b]++;
}
int[] res = new int[n];
if (!bfs(n, res, inDegrees)) {
System.out.println(-1);
} else {
for (int i : res) {
System.out.print(i + " ");
}
}
}
public static boolean bfs(int n, int[] res, int[] inDegrees) {
Queue<Integer> queue = new LinkedList<>();
int index = 0;
for (int i = 1; i <= n; i++) {
if (inDegrees[i] == 0) queue.offer(i);
}
while (!queue.isEmpty()) {
int curNode = queue.poll();
res[index++] = curNode;
for (int nextIndex = h[curNode]; nextIndex != -1; nextIndex = ne[nextIndex]) {
int nextNode = e[nextIndex];
if (--inDegrees[nextNode] == 0) {
queue.offer(nextNode);
}
}
}
return index == n;
}
public static void init(int n, int m) {
idx = 0;
h = new int[n + 1];
Arrays.fill(h, -1);
ne = new int[m];
e = new int[m];
}
public static void add(int a, int b) {
ne[idx] = h[a];
h[a] = idx;
e[idx] = b;
idx++;
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla