@Test public void randomTest() { int N = 300; Random r = new Random(); for (int i = 5; i < N; i += r.nextInt(10)) { int v = r.nextInt(i) + i; Digraph G = DigraphGenerator.dag(v, r.nextInt(v * (v - 1) / 2)); Assert.assertEquals(expect(G), HamilitonianPathInDAG.solve(GraphConverter.convert(G))); } }
public static List<Integer> solve(Set<Integer>[] DAG) { LinkedList<Integer> res = new LinkedList<>(); int n = DAG.length; boolean[] seen = new boolean[n]; for (int i = 0; i < n; i++) { if (seen[i]) continue; dfs(DAG, i, seen, res); } int pre = -1; for (int k : res) { if (pre != -1 && !DAG[pre].contains(k)) { return new ArrayList<>(); } pre = k; } return res; }
HamilitonianPathInDAG { public static List<Integer> solve(Set<Integer>[] DAG) { LinkedList<Integer> res = new LinkedList<>(); int n = DAG.length; boolean[] seen = new boolean[n]; for (int i = 0; i < n; i++) { if (seen[i]) continue; dfs(DAG, i, seen, res); } int pre = -1; for (int k : res) { if (pre != -1 && !DAG[pre].contains(k)) { return new ArrayList<>(); } pre = k; } return res; } }
HamilitonianPathInDAG { public static List<Integer> solve(Set<Integer>[] DAG) { LinkedList<Integer> res = new LinkedList<>(); int n = DAG.length; boolean[] seen = new boolean[n]; for (int i = 0; i < n; i++) { if (seen[i]) continue; dfs(DAG, i, seen, res); } int pre = -1; for (int k : res) { if (pre != -1 && !DAG[pre].contains(k)) { return new ArrayList<>(); } pre = k; } return res; }  }
HamilitonianPathInDAG { public static List<Integer> solve(Set<Integer>[] DAG) { LinkedList<Integer> res = new LinkedList<>(); int n = DAG.length; boolean[] seen = new boolean[n]; for (int i = 0; i < n; i++) { if (seen[i]) continue; dfs(DAG, i, seen, res); } int pre = -1; for (int k : res) { if (pre != -1 && !DAG[pre].contains(k)) { return new ArrayList<>(); } pre = k; } return res; }  static List<Integer> solve(Set<Integer>[] DAG); }
HamilitonianPathInDAG { public static List<Integer> solve(Set<Integer>[] DAG) { LinkedList<Integer> res = new LinkedList<>(); int n = DAG.length; boolean[] seen = new boolean[n]; for (int i = 0; i < n; i++) { if (seen[i]) continue; dfs(DAG, i, seen, res); } int pre = -1; for (int k : res) { if (pre != -1 && !DAG[pre].contains(k)) { return new ArrayList<>(); } pre = k; } return res; }  static List<Integer> solve(Set<Integer>[] DAG);  }