Buttercola: Git Version
Find all git commits, and print it out in order.
Solution:
Using BFS.
找两个commits 的 LCA. 先BFS搜索一个node的 parents, 然后再搜索第二个node 的 parents.
Read full article from Buttercola: Git Version
Find all git commits, and print it out in order.
Solution:
Using BFS.
public List<Integer> findCommits(GraphNode root) { List<Integer> result = new ArrayList<>(); Set<GraphNode> visited = new HashSet<>(); Queue<GraphNode> queue = new LinkedList<>(); findCommitsHelper(root, visited, queue, result); return result; } private void findCommitsHelper(GraphNode root, Set<GraphNode> visited, Queue<GraphNode> queue, List<Integer> result) { if (root == null) { return; } queue.offer(root); while (!queue.isEmpty()) { GraphNode curr = queue.poll(); if (!visited.contains(curr)) { visited.add(curr); result.add(curr.val); for (GraphNode neighbor : curr.neighbors) { queue.offer(neighbor); } } } } private GraphNode buildGraph(int[][] commits) { if (commits == null || commits.length == 0) { return null; } // step 1: constrcut the graph Map<Integer, GraphNode> map = new HashMap<>(); for (int[] commit : commits) { int from = commit[0]; int to = commit[1]; GraphNode fromNode = null; if (map.containsKey(from)) { fromNode = map.get(from); } else { fromNode = new GraphNode(from); } if (map.containsKey(to)) { GraphNode toNode = map.get(to); fromNode.neighbors.add(toNode); } else { GraphNode toNode = new GraphNode(to); fromNode.neighbors.add(toNode); map.put(to, toNode); } map.put(from, fromNode); } // Step 2: find out the root of the graph GraphNode root = null; Map<GraphNode, Integer> inDegree = new HashMap<>(); for (GraphNode node : map.values()) { if (!inDegree.containsKey(node)) { inDegree.put(node, 0); } for (GraphNode neighbor : node.neighbors) { if (inDegree.containsKey(neighbor)) { int degree = inDegree.get(neighbor); inDegree.put(neighbor, degree + 1); } else { inDegree.put(neighbor, 1); } } } for (GraphNode node : inDegree.keySet()) { if (inDegree.get(node) == 0) { root = node; break; } } System.out.println("Root is " + root.val); return root; } class GraphNode { int val; List<GraphNode> neighbors; public GraphNode(int val) { this.val = val; this.neighbors = new ArrayList<>(); } } public int findLCA(GraphNode node1, GraphNode node2) { if (node1 == null || node2 == null) { throw new NullPointerException(); } List<Integer> result1 = new ArrayList<>(); bfs(node1, result1); List<Integer> result2 = new ArrayList<>(); bfs(node2, result2); int i = result1.size() - 1; int j = result2.size() - 1; for (; i >= 0 && j >= 0; i--, j--) { if (result1.get(i) == result2.get(j)) { continue; } else { break; } } return result1.get(i + 1); } private void bfs(GraphNode root, List<Integer> result) { if (root == null) { return; } Set<GraphNode> visited = new HashSet<>(); Queue<GraphNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { GraphNode curr = queue.poll(); if (!visited.contains(curr)) { result.add(curr.val); visited.add(curr); for (GraphNode parent : curr.parents) { queue.offer(parent); } } } } static class GraphNode { int val; List<GraphNode> neighbors; List<GraphNode> parents; public GraphNode(int val) { this.val = val; this.neighbors = new ArrayList<>(); this.parents = new ArrayList<>(); } }