Print All Topology Sort

Link

本体是二流就（alien dictionary)。很快秒了，但是追加是输出所有topological sort的组合。卡在这了，

我当时的思路是DFS preprocessing每一个字母可以reach的set，做permutation，reachable的不互换。写着写着发现不对。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

package AllTopologSort; import java.util.*; public class Main { public static void main(String[] args) { System.out.println("Hello world"); Map<Character, List<Character>> links = new HashMap<>(); links.put('A', new ArrayList<>()); links.put('B', new ArrayList<>()); links.put('C', new ArrayList<>()); links.put('D', new ArrayList<>()); links.put('E', new ArrayList<>()); links.get('A').add('B'); links.get('A').add('C'); links.get('B').add('C'); Map<Character, State> states = new HashMap<>(); states.put('A', State.INITIVAL); states.put('B', State.INITIVAL); states.put('C', State.INITIVAL); states.put('D', State.INITIVAL); states.put('E', State.INITIVAL); Map<Character, Integer> degrees = new HashMap<>(); degrees.put('A', 0); degrees.put('B', 1); degrees.put('C', 2); degrees.put('D', 0); degrees.put('E', 0); printAllTopologySort(links, states, degrees, new ArrayList<>(), links.size()); } enum State { INITIVAL, VISITING, DONE } static void printAllTopologySort(Map<Character, List<Character>> links, Map<Character, State> states, Map<Character, Integer> degrees, List<Character> path, int n) { if(path.size() == n){ System.out.println(path); } for(char key : links.keySet()){ if(degrees.get(key)==0 && states.get(key)==State.INITIVAL){ for(char next : links.get(key)){ degrees.put(next, degrees.get(next)-1); } states.put(key, State.VISITING); path.add(key); printAllTopologySort(links, states, degrees, path, n); states.put(key, State.INITIVAL); for(char next : links.get(key)){ degrees.put(next, degrees.get(next)+1); } path.remove(path.size()-1); } } } }