AC Java solutions: Union-Find, BFS, DFS


  • 19
    L
    class Node{
        int val;
        Node parent;
        public Node(int val)
        {
            this.val = val;
        }
    }
    
    public class Solution {
        Map<Integer, Node> forest;
        
        public boolean validTree(int n, int[][] edges) {
            return unionFind(n, edges);
        }
        
        private boolean unionFind(int n, int[][] edges)
        {
            // make set for each node
            forest = new HashMap<Integer, Node>();
            for(int i = 0; i < n; i++)
                forest.put(i, makeSet(i));
            
            // for the two vertice of each edge, find if they are in the same set,
            // If so, there is a cycle, return false.
            for(int[] edge : edges)
            {
                if(find(edge[0]) == find(edge[1]))
                    return false;
                
                union(edge[0], edge[1]);
            }
            
            return edges.length == n - 1;
        }
        
        private Node makeSet(int val)
        {
            Node node = new Node(val);
            node.parent = node;
            return node;
        }
        
        private Node find(int node)
        {
            if(forest.get(node).parent.val == node)
                return forest.get(node);
            
            return find(forest.get(node).parent.val);
        }
        
        private void union(int node1, int node2)
        {
            Node set1 = find(node1);
            Node set2 = find(node2);
            set1.parent = set2;
        }
        
        // DFS, using stack
        private boolean validDFS(int n, int[][] edges)
        {
            // build the graph using adjacent list
            List<Set<Integer>> graph = new ArrayList<Set<Integer>>();
            for(int i = 0; i < n; i++)
                graph.add(new HashSet<Integer>());
            for(int[] edge : edges)
            {
                graph.get(edge[0]).add(edge[1]);
                graph.get(edge[1]).add(edge[0]);
            }
            
            // no cycle
            boolean[] visited = new boolean[n];
            Deque<Integer> stack = new ArrayDeque<Integer>();
            stack.push(0);
            while(!stack.isEmpty())
            {
                int node = stack.pop();
                if(visited[node])
                    return false;
                visited[node] = true;
                for(int neighbor : graph.get(node))
                {
                    stack.push(neighbor);
                    graph.get(neighbor).remove(node);
                }
            }
            
            // fully connected
            for(boolean result : visited)
            {
                if(!result)
                    return false;
            }
            
            return true;
        }
        
        // BFS, using queue
        private boolean valid(int n, int[][] edges)
        {
            // build the graph using adjacent list
            List<Set<Integer>> graph = new ArrayList<Set<Integer>>();
            for(int i = 0; i < n; i++)
                graph.add(new HashSet<Integer>());
            for(int[] edge : edges)
            {
                graph.get(edge[0]).add(edge[1]);
                graph.get(edge[1]).add(edge[0]);
            }
            
            // no cycle
            boolean[] visited = new boolean[n];
            Queue<Integer> queue = new ArrayDeque<Integer>();
            queue.add(0);
            while(!queue.isEmpty())
            {
                int node = queue.poll();
                if(visited[node])
                    return false;
                visited[node] = true;
                for(int neighbor : graph.get(node))
                {
                    queue.offer(neighbor);
                    graph.get(neighbor).remove((Integer)node);
                }
            }
            
            // fully connected
            for(boolean result : visited)
            {
                if(!result)
                    return false;
            }
            
            return true;
        }
    }

  • 1
    Z

    In the BFS one, while loop can't not detect loop, try{ [1, 2] [2, 3] [1, 3]}:

    boolean[] visited = new boolean[n];
            Queue<Integer> queue = new ArrayDeque<Integer>();
            queue.add(0);
            while(!queue.isEmpty())
            {
                int node = queue.poll();
                if(visited[node])
                    return false;
                visited[node] = true;
                for(int neighbor : graph.get(node))
                {
                    queue.offer(neighbor);
                    graph.get(neighbor).remove((Integer)node);
                }
            }
    

    Should be:

    boolean[] visited = new boolean[n];
            Queue<Integer> queue = new ArrayDeque<Integer>();
            queue.add(0);
            while(!queue.isEmpty())
            {
                int node = queue.poll();
                for(int neighbor : graph.get(node))
                {
                    if(visited[neighbor])
                        return false;
                    visited[neighbor] = true;                
                    queue.offer(neighbor);
                    graph.get(neighbor).remove((Integer)node);
                }
            }

  • 0
    Y

    @zjh08177
    seems not true. ran his version with our test case returned false.


Log in to reply
 

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