Course Schedule II

拓扑排序. 求排序后的结果.

我用的是in-degree数组做法, 一共运行n次, 每次都查找是否有in-degree为0 的点, 如果有, 标记-1(visited), 然后更新相关的边. 用一个into数组, 记录into边的数量, 即可知道是否当前访问的点的所有边都搜索过了. 这个做法简练, 而且不用dfs/bfs什么的那么多数据结构.

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;
    }
}