Share my [25-line DFS], [20-line BFS] and [clean Union-Find] Java solutions


  • 32
    M

    Check 2 things: 1. whether there is loop 2. whether the number of connected components is 1


    DFS

    public class Solution {
        public boolean validTree(int n, int[][] edges) {
            int[] visited = new int[n];
            List<List<Integer>> adjList = new ArrayList<>();
            for (int i=0; i<n; ++i) { adjList.add(new ArrayList<Integer>()); }
            for (int[] edge: edges) {
                adjList.get(edge[0]).add(edge[1]);
                adjList.get(edge[1]).add(edge[0]);
            }
            if (hasCycle(-1, 0, visited, adjList)) { return false; }  // has cycle
            for (int v: visited) { if (v == 0) { return false; } }  // not 1 single connected component
            return true;
        }
        
        private boolean hasCycle(int pred, int vertex, int[] visited, List<List<Integer>> adjList) {
            visited[vertex] = 1;  // current vertex is being visited
            for (Integer succ: adjList.get(vertex)) {  // successors of current vertex
                if (succ != pred) {  // exclude current vertex's predecessor
                    if (visited[succ] == 1) { return true; }  // back edge/loop detected!
                    else if (visited[succ] == 0) {
                        if (hasCycle(vertex, succ, visited, adjList)) { return true; }
                    }
                }
            }
            visited[vertex] = 2;
            return false;
        }
    }
    

    BFS

    public class Solution {
        public boolean validTree(int n, int[][] edges) {
            int[] visited = new int[n];
            List<List<Integer>> adjList = new ArrayList<>();
            for (int i=0; i<n; ++i) { adjList.add(new ArrayList<Integer>()); }
            for (int[] edge: edges) {
                adjList.get(edge[0]).add(edge[1]);
                adjList.get(edge[1]).add(edge[0]);
            }
            Deque<Integer> q = new ArrayDeque<>();
            q.addLast(0); visited[0] = 1;  // vertex 0 is in the queue, being visited
            while (!q.isEmpty()) {
                Integer cur = q.removeFirst();
                for (Integer succ: adjList.get(cur)) {
                    if (visited[succ] == 1) { return false; }  // loop detected
                    if (visited[succ] == 0) { q.addLast(succ); visited[succ] = 1; }
                }
                visited[cur] = 2;  // visit completed
            }
            for (int v: visited) { if (v == 0) { return false; } }  // # of connected components is not 1
            return true;
        }
    }
    

    Union-Find with path compression and merge by rank

    public class Solution {
        
        class UnionFind {
            
            int[] parent;
            int[] rank;
            int count;
            
            UnionFind(int n) {
                parent = new int[n];
                rank = new int[n];
                count = n;  // number of components
                for (int i=0; i<n; ++i) { parent[i] = i; }  // initially, each node's parent is itself.
            }
            
            int find(int x) {
                if (x != parent[x]) {
                    parent[x] = find(parent[x]);  // find root with path compression
                }
                return parent[x];
            }
            
            boolean union(int x, int y) {
                int X = find(x), Y = find(y);
                if (X == Y) { return false; }
                if (rank[X] > rank[Y]) { parent[Y] = X; }  // tree Y is lower
                else if (rank[X] < rank[Y]) { parent[X] = Y; }  // tree X is lower
                else {  // same height
                    parent[Y] = X;
                    ++rank[X];
                }
                --count;
                return true;
            }
        }
        
        public boolean validTree(int n, int[][] edges) {
            UnionFind uf = new UnionFind(n);
            for (int[] edge: edges) {
                int x = edge[0], y = edge[1];
                if (!uf.union(x, y)) { return false; }  // loop detected
            }
            return uf.count == 1;
        }
    }

  • 0
    B

    really nice code


  • 2
    Y

    Hi, why we need visited[vertex] = 2?


  • 0
    M

    thanks.........


  • 0
    M

    Hi. In order to pass the tests, I don't think we need it. On the other hand, I prefer the states (unvisited, being visited, visited) look like what they actually are after program execution. Consistency is what I'd like to have :)


  • 0
    J

    thx for your solution ~ really neatly organized !

    your profile pic reminded me of "when i was young and 'bold' and strong" lol


  • 0
    B

    Could you explain how you come up with the way to check cycle? I haven't seen this before. Thanks!


  • 0
    M

    @jiaodong :anger_right:


  • 1
    M

    @brookc alt text
    Take a look at edge BA here.

    Starting from A, since there exists back edge B->A, when traversing DFS path A-->B-->A, A is visited for a second time. Namely, A is visited AT THE SAME TIME it is still in the DFS recursion stack. Loop detected.


  • 0
    J

    @brookc It's on CLRS(3rd edition) , Chapter 22, Elementary Graph Algorithms, this chapter includes BFS and DFS with three colored states.


  • 0
    G

    Thanks for the nice code! But I think "visited[vertex] = 2" is not needed


  • 1
    M

    @genius1wjc yes, you are right. it is not needed. but i think it is also good to set the state correct... anyway, this is just my personal preference.


  • 0
    Y

    @genius1wjc
    @mach7
    From my point of view, the "visited[vertex] = 2" is needed because, the code is using adjacent matrix to present the undirected graph. Hence there is an A->B if there is a B->A. When you visited A and add B to the queue. If A's status doesn't change, then in next iteration, B will traverse back to A whose status is still 1 and returns false. Error happens.
    So I think status changes to 2 is a must.


  • 0
    G

    @YuaoLiu He has already changed "visited[vertex]" to 1 when he started visiting the vertex, thus changing it again right before the end of visiting the vertex to 2 is not necessary.


  • 0
    Y

    @genius1wjc
    Yes, a pred variable is used to prevent the problem I said in DFS but in BFS setting to 2 is still a must.


  • 0
    C

    @mach7 As for if (visited[succ] == 1) { return true; } // back edge/loop detected! in DFS, I tried visited[succ] == 1 and visited[succ] >= 1, all of them work. I am confused what is the difference between ``visited[succ] == 1andvisited[succ] ==2```. Thanks


  • 1
    T

    For the BFS solution in this problem, I believe you can do the following thing to avoid setting visited[cur] = 2, :

    when visited[succ] == 1, instead of return false, just continue;

    we just need to make sure (1) n == edges.length - 1 (check it at the very beginning of the code) and (2) for all the int v in visited, no 0 exist.

    The reason is for a tree (1) for n nodes there must be edges.length + 1 edges and (2) if there is a cycle in it, there is no way to connect all n nodes with edges.length+1 edges.
    So there you go.


Log in to reply
 

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