Buttercola: Zenefits: Validate a Directed Graph Tree
Understand the problem:If the graph is undirected graph, it would be the same as the Leetcode question : Graph Valid Tree.
http://buttercola.blogspot.com/2015/08/leetcode-graph-valid-tree.html
The corner case which need to be very careful is if the graph contains more than one connected components, i.e. multiple islands. In this case, the graph is not a valid tree because a tree can have one and only one root.
The same role applies to the directed graph. For a directed graph, we can do a topological sorting. If a valid topological sorting exists, it means the graph does not contain a circle.
But how to deal with multiple connected components?
One solution is to calculate the in-degree for each node. For a valid tree, there should be one and only one node with in-degree 0. If not, e.g. there are two nodes with in-degree 0, the graph must not be a valid tree. Then we can also do a topological sort from this root node, avoiding starting from each and every node.
Read full article from Buttercola: Zenefits: Validate a Directed Graph Tree
Understand the problem:If the graph is undirected graph, it would be the same as the Leetcode question : Graph Valid Tree.
http://buttercola.blogspot.com/2015/08/leetcode-graph-valid-tree.html
The corner case which need to be very careful is if the graph contains more than one connected components, i.e. multiple islands. In this case, the graph is not a valid tree because a tree can have one and only one root.
The same role applies to the directed graph. For a directed graph, we can do a topological sorting. If a valid topological sorting exists, it means the graph does not contain a circle.
But how to deal with multiple connected components?
One solution is to calculate the in-degree for each node. For a valid tree, there should be one and only one node with in-degree 0. If not, e.g. there are two nodes with in-degree 0, the graph must not be a valid tree. Then we can also do a topological sort from this root node, avoiding starting from each and every node.
public static boolean validTree(int n, int[][] edges) { if (n <= 0 || edges == null || edges.length == 0) { return false; } // Step 1: calculate the in-degree for each vertex, to find out the root of the tree Map<Integer, Integer> inDegree = new HashMap<>(); for (int[] edge: edges) { if (!inDegree.containsKey(edge[1])) { inDegree.put(edge[1], 1); } else { int val = inDegree.get(edge[1]); inDegree.put(edge[1], val + 1); } } // Iterate the inDegree and check 0 degree vertex int root = 0; int count = 0; for (int i = 0; i < n; i++) { if (!inDegree.containsKey(i)) { root = i; count++; } } if (count != 1) { return false; } // Step 2: transform the edge list to the adjlist Map<Integer, List<Integer>> adjList = new HashMap<>(); for (int[] edge : edges) { if (adjList.containsKey(edge[0])) { List<Integer> neighbors = adjList.get(edge[0]); neighbors.add(edge[1]); } else { List<Integer> neighbors = new ArrayList<>(); neighbors.add(edge[1]); adjList.put(edge[0], neighbors); } } boolean[] visited = new boolean[n]; return validTreeHelper(root, visited, adjList); } private static boolean validTreeHelper(int vertexId, boolean[] visited, Map<Integer, List<Integer>> adjList) { if (visited[vertexId]) { return false; } visited[vertexId] = true; List<Integer> neighbors = adjList.get(vertexId); if (neighbors != null) { for (int neighbor : neighbors) { if (!validTreeHelper(neighbor, visited, adjList)) { return false; } } } visited[vertexId] = false; return true; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int numVertices = scanner.nextInt(); int numEdges = scanner.nextInt(); int[][] edges = new int[numEdges][2]; for (int i = 0; i < numEdges; i++) { edges[i][0] = scanner.nextInt(); edges[i][1] = scanner.nextInt(); } boolean result = Solution.validTree(numVertices, edges); System.out.println(result); scanner.close(); }