Course Schedule II
拓扑排序. 求排序后的结果.
我用的是in-degree数组做法, 一共运行n次, 每次都查找是否有in-degree为0 的点, 如果有, 标记-1(visited), 然后更新相关的边. 用一个into数组, 记录into边的数量, 即可知道是否当前访问的点的所有边都搜索过了. 这个做法简练, 而且不用dfs/bfs什么的那么多数据结构.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Solution { public int[] findOrder(int n, int[][] p) { int[] into = new int[n]; for(int[] pp : p) into[pp[0]]++; int[] res = new int[n]; int k = 0; for(int i = 0; i < n; i++) { int j = 0; while(j < n) { if(into[j] == 0) break; j++; } if(j == n) return new int[0]; res[k++] = j; into[j] = -1; for(int[] pp : p) if(pp[1] == j) { into[pp[0]]--; } } return res; } } |