public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
ArrayList<DirectedGraphNode> res = new ArrayList<>();
if (graph == null || graph.size() == 0) {
return res;
}
// collect in-degree
HashMap<DirectedGraphNode, Integer> inDegree = new HashMap<>();
for (DirectedGraphNode node : graph) {
for (DirectedGraphNode nei : node.neighbors) {
if (inDegree.containsKey(nei)) {
inDegree.put(nei, inDegree.get(nei) + 1);
} else {
inDegree.put(nei, 1);
}
}
}
// put all indegree == 0 point in the result, also put in queue for tranvesal
Queue<DirectedGraphNode> queue = new LinkedList<>();
for (DirectedGraphNode node : graph) {
if (!inDegree.containsKey(node)) {
res.add(node);
queue.offer(node);
}
}
// do bfs and add ndoe to result
while (!queue.isEmpty()) {
DirectedGraphNode cur = queue.poll();
for (DirectedGraphNode nei : cur.neighbors) {
inDegree.put(nei, inDegree.get(nei) - 1);
if (inDegree.get(nei) == 0) {
inDegree.remove(nei);
queue.offer(nei);
res.add(nei);
}
}
}
if (inDegree.size() != 0) {
// don't have topo order
}
return res;
}