Concise JAVA solution based on DFS


  • 0

    Solution1. Backtracking

    The basic idea is to use DFS to check if the current node was already included in the traveling path. In this case, we need to convert graph presentation from edge list to adjacency list first, and then check if there's cycle existing in any subset. Because tree is a connected graph, we can start from any node.

    As the following:

    public boolean validTree(int n, int[][] edges) {
        if (edges.length != 0) { 
            HashMap<Integer, HashSet<Integer>> neighbors = new HashMap<Integer, HashSet<Integer>>(); // Neighbors of each node 
        	HashSet<Integer>curPath = new HashSet<Integer>(); // Nodes on the current path
        	for (int i = 0; i < edges.length; i++) {// Convert graph presentation from edge list to adjacency list 
        		if (!neighbors.containsKey(edges[i][0])) neighbors.put(edges[i][0], new HashSet<Integer>());  
        		if (!neighbors.containsKey(edges[i][1])) neighbors.put(edges[i][1], new HashSet<Integer>());      		
        		neighbors.get(edges[i][0]).add(edges[i][1]);
        		neighbors.get(edges[i][1]).add(edges[i][0]);
        	}
            if (hasCycle(neighbors, edges[0][0], -1, curPath))// Use DFS method to check if there's cycle in any curPath
                return false;
        } 
        return edges.length == n - 1;
    }
    
    boolean hasCycle(HashMap<Integer, HashSet<Integer>> neighbors, int kid, int parent, HashSet<Integer>curPath) {
        if (curPath.contains(kid)) return true;// The current node is already in the set of the current path
        curPath.add(kid);
        
        for (Integer neighbor : neighbors.get(kid))
            if (neighbor != parent && hasCycle(neighbors, neighbor, kid, curPath))// DFS 
                return true;
        curPath.remove(kid);
        return false;
    }
    

    Solution2. Union Find
    Union Find is 1-Dimension memorized DFS(): travel from every node to leaf, if the leaf equals any node on the path, then there's cycle

     public boolean validTree(int n, int[][] edges) {
            int[] leaves = new int[n];// leaves[i]: i's leaf
            Arrays.fill(leaves, -1);
    
            for (int i = 0; i < edges.length; i++) {
                int src = findLeaf(leaves, edges[i][0]);
                int dst = findLeaf(leaves, edges[i][1]);
    
                if (src == dst) 
                	return false;
                	
                //Union: Merge two sets which doesn't overlap
                leaves[src] = dst;
            }
            return edges.length == n - 1;
        }
    
        //find i's leaf
        int findLeaf(int leaves[], int i) {
            if (leaves[i] == -1) return i; //-1 means reach the leaf
            return findLeaf(leaves, leaves[i]);
        }  
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.