题解 | JAVA #检测循环依赖# [P0-T2]

拓扑排序

三个数据存储的内容：
   infosMap: 还没安排的课(以及该门课的上下游依赖关系)
      inEdge: 还没上的上游课程的数量
        inEdge==0表示这门课不依赖其他课，或者依赖的课已经上过了(i.e. 加入ans了)
      neis: 下游的课号
   queue: 安排了将要上的课。
   ans: 已经上过的课。
   
1. 整理input, 建立infosMap:
   
2. 遍历infos, 将inEdge==0的课加入queue。
   i.e. 该课不依赖其他课，直接安排上。

3. 逐一上掉安排了的课
   假设上掉的课是x, x.neis = [y,z], 那么y,z的inEdge减1
   如果y,z此时inEdge也等于0了，表示y,z也可以安排了，enqueue.  

import java.util.*;

// topological sort
public class Solution {
  
   class Info {
    int nodeId;
    int inEdge = 0;
    final List<Integer> neis = new ArrayList<>();
    Info(int id) {
      nodeId = id;
    }
  }
  
  public int[] findOrder (int[][] prerequisites, int n) {
    Map<Integer, Info> infos = new HashMap<>();
    for (int i = 0; i < n; i++) 
      infos.put(i, new Info(i));
    for (int[] pre : prerequisites) {
      int from = pre[1], to = pre[0];
      infos.get(from).neis.add(to);
      infos.get(to).inEdge++;
    }
    
    Queue<Info> q = new LinkedList<>();
    Iterator<Map.Entry<Integer, Info>> it = infos.entrySet().iterator();
    while(it.hasNext()) {
      Map.Entry<Integer, Info> entry = it.next();
      Info info = entry.getValue();
      if (info.inEdge == 0) {
        q.offer(info);  // enqueue roots
        it.remove();  // remove 0 inEdge node
      }
    }
    
    List<Integer> ans = new ArrayList<>();
    while (!q.isEmpty()) {
      Info cur = q.poll();
      ans.add(cur.nodeId);
      for (int nei : cur.neis) {
        Info neiInfo = infos.get(nei);
        if (neiInfo == null) continue;
        if (--neiInfo.inEdge == 0) {
          infos.remove(neiInfo.nodeId);
          q.offer(neiInfo);  // remove 0 inEdge node
        }
      }
    }
    
    return ans.stream().mapToInt(x->x).toArray();
  }
}