/** * Definition for Directed graph. * class DirectedGraphNode { * int label; * ArrayList<DirectedGraphNode> neighbors; * DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); } * }; */publicclassSolution { /** * @param graph: A list of Directed graph node * @return: Any topological order for the given graph. */publicArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {// write your code hereArrayList<DirectedGraphNode> list =newArrayList<DirectedGraphNode>();HashSet<DirectedGraphNode> set =newHashSet<DirectedGraphNode>();for(DirectedGraphNode root : graph){if(!set.contains(root)) dfs(list, set, root); }// 现在的 list 是由若干个顺序倒转的 topological order list 组成的// 这里的处理类似于 reverse words in a string// 把每个单词单独翻转之后,再把整个句子翻转Collections.reverse(list);return list; }privatevoiddfs(ArrayList<DirectedGraphNode> list,HashSet<DirectedGraphNode> set,DirectedGraphNode root){set.add(root);for(DirectedGraphNode node :root.neighbors){if(!set.contains(node)) dfs(list, set, node); }// 到这一步,root 节点的所有 sub path 都已经被访问过了// 最后才在 list 中添加元素,得到的是一个反序的 topological orderlist.add(root); }}
做了欧拉回路之后,发现一个更好的做法是直接建 LinkedList,然后用 addFirst();
熟练使用 API 很重要啊~
publicArrayList<DirectedGraphNode>topSort(ArrayList<DirectedGraphNode> graph) {// write your code hereLinkedList<DirectedGraphNode> list =newLinkedList<DirectedGraphNode>();HashSet<DirectedGraphNode> visited =newHashSet<DirectedGraphNode>();for(DirectedGraphNode root : graph){dfs(list, root, visited); }returnnewArrayList<DirectedGraphNode>(list); }privatevoiddfs(LinkedList<DirectedGraphNode> list,DirectedGraphNode root,HashSet<DirectedGraphNode> visited){if(visited.contains(root)) return;for(DirectedGraphNode next :root.neighbors){dfs(list, next, visited); }list.addFirst(root);visited.add(root); }