算法思想
如果是一个有向无环图,一定存在一个入度为0的点,先把入度为0的点加入到队列中去,然后把这个点的所有出度去除,这样的话会出现新的入度为0的点,再把这个点加入到队列中去,依次循环
举例:模板题中的例子,1指向2,2指向3,1指向3
首先的话,1的入度为0,2的入度为1,3的入度为2;
所以我们先把1加入到队列中去,然后把1的所有出度去除,也就是2的入度变成了0,3的入度变成了1;
然后我们再把2加入到队列中去,3的入度变成了0;再把3加入到队列中,然后发现队列的大小为0,说明遍历完了,就可以输出结果了;
我在学完树和图的遍历后,发现一知半解,原因在于,对树的存储的理解很朦胧,于是拿着实际的例子放到代码中,才得以理解,但是这样的方法,拿着实例去模拟,是很耗费时间的,先记录一下,不知道以后会有没有更好的办法去理解
首先要理解树的存储,就要理解每个数组的含义,不妨把第一个节点设为a,第二个节点设为b
1:h[]以第一个节点a为索引,存储当前操作的节点idx(idx从0开始)
2:e[]以当前操作的节点idx为索引,存储第二个节点b
3:ne[]以当前操作的节点idx为索引,存储每个单链表的头节点h[k]
4:d[]以每个节点的编号为索引,存储每个节点的入度
树的存储是有h[],e[],ne[],idx构成的,我们可以发现每个数组都与idx有关系,所以我们可以通过idx得到所有信息
知道了所有数组的具体含义,那么代码也就很清楚了,可以跟着下面的图模拟一遍代码,
我这里用的是java原生的队列Queue,没有用数组模拟,因为多个知识点混在一起,很容易弄混,分开来就会清晰一些
Java代码
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
public class Main{
static int N = 100010;
static int[] h = new int[N]; //以第一个节点的编号为索引,存储所有单链表的头节点
static int[] e = new int[N]; //以当前要操作的节点为索引,存储第二个节点的编号
static int[] ne = new int[N]; //以当前操作的节点为索引,存储下一个节点
static int[] d = new int[N]; //存储i号节点的入度
static int[] top = new int[N];
static Queue<Integer> q = new LinkedList<>();
static int idx,n,cnt = 1; //cnt指的是top中有多少元素
public static void main(String[] args){
Scanner in = new Scanner(System.in);
n = in.nextInt();
int m = in.nextInt();
for(int i = 0; i < N; i ++) h[i] = -1;
for(int i = 0; i < m; i ++)
{
int a = in.nextInt();
int b = in.nextInt();
add(a,b);
d[b]++; //入度+1
}
if(topsort())
{
for(int i = 1; i <= n; i ++) System.out.print(top[i] + " ");
}
else System.out.print("-1");
}
private static void add(int a ,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
private static boolean topsort()
{
for(int i = 1; i <= n; i ++) //因为是从1开始编号的,所以从1开始遍历
{
if(d[i] == 0) q.offer(i); //遍历每个节点,入度为0就入栈
}
while(q.size() != 0)
{
int t = q.poll();
top[cnt] = t;
cnt++;
for(int i =h[t]; i != -1; i = ne[i]) //遍历链表,删除1的所有出度
{
int j = e[i]; //j找到第一个节点指向的点b
if(--d[j] == 0) q.offer(j); //删除边
}
}
return cnt >= n; //注意这里一定是>=,因为cnt = 3以后会++等于4
}
}
cnt只能等于n+1吧?
return cnt==n+1 ;
数据被加强了,现在有仅有一个顶点和两个自环的样例,条件改成cnt >= n&&n!=1
谢谢教程,顺便给其他java用户注意:这题卡List, 只能用top这个int[]数组接收结果,用list就TLE超时。
代码里idx不是初始化是1吗?
不是删除所有出度吧,该节点的子节点的入度-1
谢谢您的指出!!这两个说法是等价的,即删除该节点的所有出度 = 该节点的子节点的入度-1,只不过角度不同
比如说删除1的所有出度,对于1来说,指的是把1—>2,1—>3两条边删除,也就是所有出度;
对于子节点来说,指的是1的子节点(2,3)的入度-1
这样啊 懂懂懂