Graph Valid Tree

Medium

Question

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

Notice

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Tags

Depth First Search Facebook Zenefits Union Find Breadth First Search Google

Related Problems

Medium Find the Connected Component in the Undirected Graph

Analysis

According to the definition of tree on Wikipedia:

“a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

DFS, BFS均可以解此题，有趣的是Union Find的解法。// TODO: Add DFS, BFS

This problem can be converted to finding a cycle in a graph. It can be solved by using DFS (Recursion) or BFS (Queue).

Union Find 思路

初始化Union Find的father map，让每一个节点的初始parent指向自己（自己跟自己是一个Group）；在循环读取edge list时，查找两个节点的parent，如果相同，说明形成了环（Cycle），那么这便不符合树（Tree）的定义，反之，如果不相同，则将其中一个节点设为另一个的parent，继续循环。

此外还有需要注意的是对于vertex和edge的validation，|E| = |V| - 1，也就是要验证 edges.length == n - 1，如果该条件不满足，则Graph一定不是valid tree。

DFS / BFS

把输入的edge list转化为adjacency list，便于基于vertex的搜索。

BFS

在于每次遍历邻接表时，对于node的neighbor，放入BFS的queue中之后，就把node本身从neighbor的邻接表中移除。

for(int neighbor : graph.get(node))
{
    queue.offer(neighbor);
    graph.get(neighbor).remove((Integer)node);
}

或者，只在neighbor没有被遍历过时才放入queue中：

for(int i: map.get(top)){
    // only putting new node into the queue
    if(!visited[i])
    queue.offer(i);
}

这样，在遍历出队列时，如果遇到元素被二次访问就说明有cycle。

// check cycle
int top = queue.poll();
if(visited[top]) return false;

最后遍历visited[]，确认每一个元素都被遍历到，才是valid tree（没有落单的节点）

// fully connected
for(boolean b: visited){
    if(!b) return false;
}

DFS

DFS 类似，只是在recursive放入parent和当前节点curr时，选择curr != parent才进行下一层hasCycle的递归，这样如果出现二次访问，就说明了有cycle。

Solution

Union Find Solution

public class Solution {
    class UnionFind {
        // Implemented with array instead of HashMap for simplicity
        int[] parent;

        // Constructor
        UnionFind (int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            return compressed_find(x);
        }

        public int compressed_find(int x) {
            int x_parent = parent[x];
            while (x_parent != parent[x_parent]) {
                x_parent = parent[x_parent];
            }

            int temp = -1;
            int t_parent = parent[x];
            while (t_parent != parent[t_parent]) {
                temp = parent[t_parent];
                parent[t_parent] = x_parent;
                t_parent = temp;
            }
            return x_parent;
        }
        public void union(int x, int y) {
            int x_parent = find(x);
            int y_parent = find(y);
            if (x_parent != y_parent) {
                parent[x_parent] = y_parent;
            }
        }
    }
    /**
     * @param n an integer
     * @param edges a list of undirected edges
     * @return true if it's a valid tree, or false
     */
    public boolean validTree(int n, int[][] edges) {
        // Validation of |V| - 1 = |E|
        if (n - 1 != edges.length || n == 0) {
            return false;
        }
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < edges.length; i++) {
            if (uf.find(edges[i][0]) == uf.find(edges[i][1])) {
                return false;
            }
            uf.union(edges[i][0], edges[i][1]);
        }
        return true;
    }
}

Simplified Union Find (0ms 100%)

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;

        int[] parent = new int[n];
        Arrays.fill(parent, -1);

        for (int[] edge : edges) {
            int x = find(edge[0], parent);
            int y = find(edge[1], parent);

            if (x == y) return false;
            parent[x] = y;
        }

        return true;
    }

    int find(int node, int[] parent) {
        if (parent[node] == -1) return node;

        return parent[node] = find(parent[node], parent);
    }
}

Union Find - with path compression and weighted (1ms, 74.31%)

class Solution {
    public class UnionFind {
        int[] parent;
        int[] rank;
        int count;

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
            count = n;
        }

        public int find (int p) {
            int root = p;
            while (parent[p] != p) {
                parent[p] = parent[parent[p]];
                p = parent[p];
            }
            return p;
        }

        public void union(int a, int b) {
            int rootA = find(a);
            int rootB = find(b);
            if (rootA == rootB) {
                return;
            }
            if (rank[rootA] > rank[rootB]) {
                parent[rootB] = rootA;
                rank[rootA] += rank[rootB];
            } else {
                parent[rootA] = rootB;
                rank[rootB] += rank[rootA];
            }
            count--;
        }

        public int getCount() {
            return count;
        }
    }
    public boolean validTree(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        for (int[] edge: edges) {
            if (uf.find(edge[0]) == uf.find(edge[1])) {
                return false;
            }
            uf.union(edge[0], edge[1]);
        }
        return uf.getCount() == 1;
    }
}

DFS Solution

public boolean validTree(int n, int[][] edges) {
    HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
    for(int i=0; i<n; i++){
        ArrayList<Integer> list = new ArrayList<Integer>();
        map.put(i, list);
    }

    for(int[] edge: edges){
        map.get(edge[0]).add(edge[1]);
        map.get(edge[1]).add(edge[0]);
    }

    boolean[] visited = new boolean[n];

    if(!helper(0, -1, map, visited))
        return false;

    for(boolean b: visited){
        if(!b)
            return false;
    }

    return true;
}

public boolean helper(int curr, int parent, HashMap<Integer, ArrayList<Integer>> map, boolean[] visited){
    if(visited[curr])
        return false;

    visited[curr] = true;

    for(int i: map.get(curr)){
        if(i!=parent && !helper(i, curr, map, visited)){
            return false;
        }
    }   

    return true;
}

DFS - another one

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        // initialize adjacency list
        List<List<Integer>> adjList = new ArrayList<List<Integer>>(n);

        // initialize vertices
        for (int i = 0; i < n; i++)
            adjList.add(i, new ArrayList<Integer>());

        // add edges    
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0], v = edges[i][1];
            adjList.get(u).add(v);
            adjList.get(v).add(u);
        }

        boolean[] visited = new boolean[n];

        // make sure there's no cycle
        if (hasCycle(adjList, 0, visited, -1))
            return false;

        // make sure all vertices are connected
        for (int i = 0; i < n; i++) {
            if (!visited[i]) 
                return false;
        }

        return true;
    }

    // check if an undirected graph has cycle started from vertex u
    boolean hasCycle2(List<List<Integer>> adjList, int u, boolean[] visited, int parent) {
        if (visited[u]) {
            return true;
        }

        visited[u] = true;

        for(int v: adjList.get(u)){
            // skip putting v into recursion again if v == parent
            if(v != parent && hasCycle(adjList, v, visited, u)){
                return true;
            }
        }

        return false;
    }

    // check if an undirected graph has cycle started from vertex u
    boolean hasCycle(List<List<Integer>> adjList, int u, boolean[] visited, int parent) {
        visited[u] = true;

        for (int i = 0; i < adjList.get(u).size(); i++) {
            int v = adjList.get(u).get(i);

            if ((visited[v] && parent != v) || (!visited[v] && hasCycle(adjList, v, visited, u)))
                return true;
        }

        return false;
    }
}

BFS Solution

public boolean validTree(int n, int[][] edges) {
    HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
    for(int i=0; i<n; i++){
        ArrayList<Integer> list = new ArrayList<Integer>();
        map.put(i, list);
    }

    for(int[] edge: edges){
        map.get(edge[0]).add(edge[1]);
        map.get(edge[1]).add(edge[0]);
    }

    boolean[] visited = new boolean[n];

    LinkedList<Integer> queue = new LinkedList<Integer>();
    queue.offer(0);
    while(!queue.isEmpty()){
        int top = queue.poll();
        if(visited[top])
            return false;

        visited[top]=true;

        for(int i: map.get(top)){
            // only putting new node into the queue
            if(!visited[i])
                queue.offer(i);
        }
    }

    // fully connected
    for(boolean b: visited){
        if(!b)
            return false;
    }

    return true;
}

BFS - Another One

    // 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;
    }
}

Reference

• LeetCode Discuss: Java Union-Find solution

• Program Creek: Graph Valid Tree (Java) DFS & BFS

• Princeton CS: Union Find