@Test public void randomTest() { long timecost1 = 0, timecost2 = 0; for (int i = 5; i < 1000; i += 50) { List<Integer>[] graph = GraphBuilder.buildEulerCycle(i); for (List<Integer> j : graph) { Collections.sort(j); } long st = System.nanoTime(); List<Integer> expect = fleury(graph); timecost1 += System.nanoTime() - st; st = System.nanoTime(); List<Integer> test = EulerCycle.solveUndirectGraph(graph); timecost2 += System.nanoTime() - st; Assert.assertEquals(expect, test); } Assert.assertTrue(timecost1 + "," + timecost2, timecost1 > 70 * timecost2); }
public static List<Integer> solveUndirectGraph(List<Integer>[] graph) { List<Integer> res = new ArrayList<>(); for (List<Integer> edge : graph) { if (edge.size() % 2 == 1) { return res; } } for (List<Integer> i : graph) { Collections.sort(i); } int n = graph.length; if (n == 0) return res; Set<Integer>[] seen = new Set[n]; for (int i = 0; i < n; i++) { seen[i] = new HashSet<>(); } LinkedList<Integer> path = new LinkedList<>(); dfs(0, graph, seen, path); return path; }
EulerCycle { public static List<Integer> solveUndirectGraph(List<Integer>[] graph) { List<Integer> res = new ArrayList<>(); for (List<Integer> edge : graph) { if (edge.size() % 2 == 1) { return res; } } for (List<Integer> i : graph) { Collections.sort(i); } int n = graph.length; if (n == 0) return res; Set<Integer>[] seen = new Set[n]; for (int i = 0; i < n; i++) { seen[i] = new HashSet<>(); } LinkedList<Integer> path = new LinkedList<>(); dfs(0, graph, seen, path); return path; } }
EulerCycle { public static List<Integer> solveUndirectGraph(List<Integer>[] graph) { List<Integer> res = new ArrayList<>(); for (List<Integer> edge : graph) { if (edge.size() % 2 == 1) { return res; } } for (List<Integer> i : graph) { Collections.sort(i); } int n = graph.length; if (n == 0) return res; Set<Integer>[] seen = new Set[n]; for (int i = 0; i < n; i++) { seen[i] = new HashSet<>(); } LinkedList<Integer> path = new LinkedList<>(); dfs(0, graph, seen, path); return path; }  }
EulerCycle { public static List<Integer> solveUndirectGraph(List<Integer>[] graph) { List<Integer> res = new ArrayList<>(); for (List<Integer> edge : graph) { if (edge.size() % 2 == 1) { return res; } } for (List<Integer> i : graph) { Collections.sort(i); } int n = graph.length; if (n == 0) return res; Set<Integer>[] seen = new Set[n]; for (int i = 0; i < n; i++) { seen[i] = new HashSet<>(); } LinkedList<Integer> path = new LinkedList<>(); dfs(0, graph, seen, path); return path; }  static List<Integer> solveUndirectGraph(List<Integer>[] graph); }
EulerCycle { public static List<Integer> solveUndirectGraph(List<Integer>[] graph) { List<Integer> res = new ArrayList<>(); for (List<Integer> edge : graph) { if (edge.size() % 2 == 1) { return res; } } for (List<Integer> i : graph) { Collections.sort(i); } int n = graph.length; if (n == 0) return res; Set<Integer>[] seen = new Set[n]; for (int i = 0; i < n; i++) { seen[i] = new HashSet<>(); } LinkedList<Integer> path = new LinkedList<>(); dfs(0, graph, seen, path); return path; }  static List<Integer> solveUndirectGraph(List<Integer>[] graph);  }