Sunday, November 1, 2015

Zenefits: Validate a Directed Graph Tree

Validate if a directed graph is a valid 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. 

Code (Java):
import java.util.*;

public class Solution {
    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();
    }
}

1 comment:

  1. To handle the case of multiple connected components, you can check if every element the array visited[] are marked to 1. Basically, all node should be reachable via root.

    ReplyDelete