拓扑序列的定义
无自闭环有向图中,被指向的节点都在指向点的后面的序列,拓扑序列不唯一。
如果一个有向图中存在自闭环,则这个图没有拓扑序列。
解题思路即步骤
1.记录每个节点的入度,被指向一次则加1;
2.开辟一个队列(该题用数组模拟队列更好);
3.遍历所有节点,将入度为0的节点添加到队列中;
4.队首出列,遍历该节点的“下一个节点”链表,将下一个节点的入度减1并判断入度是否为0,如果为0则入队列。
5.循环4操作直到队列为空。
6.判断队列元素是否与节点总数相等,如果是的话就说明该图不存在自闭环,因此存在拓扑序列。
7.此时,模拟队列数组里的元素则为拓扑序列,将该数组遍历输出即可。(此时体现了模拟队列的好处,因为所有入队的元素均会保留在数组中)
Java 代码
import java.util.*;
class Main{
public static final int N = 100010;
public static final int M = 100010;
public static int n;
public static int m;
public static int[] h = new int[N];
public static int[] ele = new int[M];
public static int[] ne = new int[M];
public static int[] d = new int[N];//记录每个点的入度
public static int[] q = new int[N];//模拟队列数组
public static int index;
public static int head;
public static int tail;
public static void add(int a,int b){
ele[index] = b;
ne[index] = h[a];
h[a] = index ++;
d[b] ++;//a指向b,b的入度加1
}
public static boolean topsort(){
//将入度为0的点加入队列
for(int i = 1;i <= n;i ++){
if(d[i] == 0){
q[tail++] = i;
}
}
while(head < tail){
int headElement = q[head ++];//队首元素出队并记录
for(int i = h[headElement];i != -1;i =ne[i]){
int j = ele[i];
d[j] --;
if(d[j] == 0){
q[tail ++] = j;
}
}
}
return tail == n;//如果队列里元素个数等于节点个数,说明不存在自闭环,也就存在拓扑序列
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
for(int i = 1;i <= n;i ++){
h[i] = -1;
}
while(m-- != 0){
int a = scan.nextInt();
int b = scan.nextInt();
add(a,b);
}
if(topsort()){
for(int i = 0;i < n;i ++){
System.out.print(q[i] + " ");
}
}else{
System.out.print(-1);
}
}
}