Buttercola: Leetcode: Graph Valid Tree

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.

For 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.

Hint:

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?
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.”

Note: 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 inedges.

Understand the problem:
A classic graph search problem. The key is first to transform from the edge list to the adjecent list. The problem is equivalent to whether the graph exists a circle. We could solve the problem by using either DFS or BFS.

A DFS solution:

public class Solution {
    public boolean validTree(int n, int[][] edges) {
         
        // Create an adj list 
        List<List<Integer>> adjList = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<Integer>());
        }
         
        for (int[] edge : edges) {
            adjList.get(edge[1]).add(edge[0]);
            adjList.get(edge[0]).add(edge[1]);
        }
         
        boolean[] visited = new boolean[n];
         
        if (!validTreeHelper(n, edges, 0, -1, visited, adjList)) {
            return false;
        }
         
        // Check the islands
        for (boolean v : visited) {
            if (!v) {
                return false;
            }
        }
         
        return true;
    }
     
    private boolean validTreeHelper(int n, int[][] edges, int vertexId, int parentId, 
                                    boolean[] visited, List<List<Integer>> adjList) {
        if (visited[vertexId]) {
            return false;
        }
         
        visited[vertexId] = true;
         
        List<Integer> neighbors = adjList.get(vertexId);
        for (Integer neighbor : neighbors) {
            if (neighbor != parentId && !validTreeHelper(n, edges, neighbor, vertexId, visited, adjList)) {
                return false;
            }
        }
         
        return true;
    }
}

A BFS solution:

public class Solution {
    public boolean validTree(int n, int[][] edges) {
         
        // Create an adj list 
        List<List<Integer>> adjList = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<Integer>());
        }
         
        for (int[] edge : edges) {
            adjList.get(edge[1]).add(edge[0]);
            adjList.get(edge[0]).add(edge[1]);
        }
         
        boolean[] visited = new boolean[n];
         
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(0);
         
        while (!queue.isEmpty()) {
            int vertexId = queue.poll();
             
            if (visited[vertexId]) {
                return false;
            }
             
            visited[vertexId] = true;
             
            for (int neighbor : adjList.get(vertexId)) {
                if (!visited[neighbor]) {
                    queue.offer(neighbor);
                }
            }
        }
         
        // Check the islands
        for (boolean v : visited) {
            if (!v) {
                return false;
            }
        }
         
        return true;
    }
}

If a graph is valid binary tree, it must follow the two conditions:
1. num of edges = num of nodes - 1
2. There is only 1 CC

BFS Solution:

public class Solution {
    /**
     * @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) {
        // write your code here
        if (n == 0) {
            return edges == null || edges.length == 0;
        }
         
        if (edges.length != n - 1) {
            return false;
        }
         
        Set<Integer> visited = new HashSet<>();
         
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }
         
        // add nodes to the adjList
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
             
            adjList.get(from).add(to);
            adjList.get(to).add(from);
        }
         
        // start bfs from each node, if it's not visited
        bfs(adjList, 0, visited);
         
        return visited.size() == n;
    }
     
    private void bfs(List<List<Integer>> adjList, int root, Set<Integer> visited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(root);
        visited.add(root);
         
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int neighbor : adjList.get(node)) {
                if (visited.contains(neighbor)) {
                    continue;
                }
                 
                queue.offer(neighbor);
                visited.add(neighbor);
            }
        }
    }
}

Update on 1/11/2021: Union-Find

public class Solution {
    /**
     * @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) {
        // write your code here
        if (n == 0) {
            return edges == null || edges.length == 0;
        }
         
        if (edges.length != n -1) {
            return false;
        }
         
        // get number of cc 
        UF uf = new UF(n);
         
        for (int[] edge : edges) {
            uf.union(edge[0], edge[1]);
        }
         
        return uf.getNumCC() == 1;
    }
}
 
class UF {
    private int n;
    private int[] parents;
    private int numCC;
     
    public UF(int n) {
        this.n = n;
        parents = new int[n];
        numCC = n;
         
        for (int i = 0; i < n; i++) {
            parents[i] = i;
        }
    }
     
    public int find(int x) {
        int root = x;
        while (parents[root] != root) {
            root = parents[root];
        }
         
        // path compression
        while (x != root) {
            int temp = parents[x];
            parents[x] = root;
            x = temp;
        }
         
        return root;
    }
     
    public void union(int x, int y) {
        int px = find(x);
        int py = find(y);
         
        if (px != py) {
            parents[px] = py;
            numCC--;
        }
    }
     
    public int getNumCC() {
        return numCC;
    }
}

Buttercola

Thursday, August 20, 2015

Leetcode: Graph Valid Tree

2 comments: