package class16; import java.util.ArrayList; import java.util.Comparator; import java.util.HashMap; // OJ链接:https://www.lintcode.com/problem/topological-sorting public class Code03_TopologicalOrderDFS1 { // 不要提交这个类 public static class DirectedGraphNode { public int label; public ArrayList neighbors; public DirectedGraphNode(int x) { label = x; neighbors = new ArrayList(); } } // 提交下面的 public static class Record { public DirectedGraphNode node; public int deep; public Record(DirectedGraphNode n, int o) { node = n; deep = o; } } public static class MyComparator implements Comparator { @Override public int compare(Record o1, Record o2) { return o2.deep - o1.deep; } } public static ArrayList topSort(ArrayList graph) { HashMap order = new HashMap<>(); for (DirectedGraphNode cur : graph) { f(cur, order); } ArrayList recordArr = new ArrayList<>(); for (Record r : order.values()) { recordArr.add(r); } recordArr.sort(new MyComparator()); ArrayList ans = new ArrayList(); for (Record r : recordArr) { ans.add(r.node); } return ans; } public static Record f(DirectedGraphNode cur, HashMap order) { if (order.containsKey(cur)) { return order.get(cur); } int follow = 0; for (DirectedGraphNode next : cur.neighbors) { follow = Math.max(follow, f(next, order).deep); } Record ans = new Record(cur, follow + 1); order.put(cur, ans); return ans; } }