Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/261.html

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

 

Example 1:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

Example 2:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false

 

Constraints:

  • 1 <= n <= 2000
  • 0 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • There are no self-loops or repeated edges.

Algorithm

If it is a tree:

  • all nodes must be connected, that is, it must be a connected graph
  • and there must be no cycles

Use queue to assist the traversal. Here, instead of using a one-dimensional vector to mark whether the node has been visited, a HashSet is used. If a node is traversed and there is no HashSet in the HashSet, the HashSet is added. If it already exists, false is returned.

Code

  • import java.util.*;
    
    public class Graph_Valid_Tree {
    
        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) {
                if (n == 0) {
                    return false;
                }
    
                if (edges.length != n - 1) { // quick check
                    return false;
                }
    
                Map<Integer, Set<Integer>> graph = initializeGraph(n, edges);
    
                // bfs
                Queue<Integer> queue = new LinkedList<>();
                Set<Integer> isVisited = new HashSet<>();
    
                queue.offer(0);
                isVisited.add(0);
                while (!queue.isEmpty()) {
                    int node = queue.poll();
                    for (Integer neighbor : graph.get(node)) {
                        if (isVisited.contains(neighbor)) { // cycle found
                            return false;
                        }
                        isVisited.add(neighbor);
                        queue.offer(neighbor);
                    }
                }
    
                return (isVisited.size() == n); // if all nodes connected
            }
    
            private Map<Integer, Set<Integer>> initializeGraph(int n, int[][] edges) {
    
                // node => its neibougher
                Map<Integer, Set<Integer>> graph = new HashMap<>();
                for (int i = 0; i < n; i++) {
                    graph.put(i, new HashSet<Integer>());
                }
    
                for (int i = 0; i < edges.length; i++) {
                    int u = edges[i][0];
                    int v = edges[i][1];
                    graph.get(u).add(v);
                    graph.get(v).add(u);
                }
    
                return graph;
            }
        }
    }
    
    ############
    
    class Solution {
        private int[] p;
    
        public boolean validTree(int n, int[][] edges) {
            p = new int[n];
            for (int i = 0; i < n; ++i) {
                p[i] = i;
            }
            for (int[] e : edges) {
                int a = e[0], b = e[1];
                if (find(a) == find(b)) {
                    return false;
                }
                p[find(a)] = find(b);
                --n;
            }
            return n == 1;
        }
    
        private int find(int x) {
            if (p[x] != x) {
                p[x] = find(p[x]);
            }
            return p[x];
        }
    }
    
  • // OJ: https://leetcode.com/problems/graph-valid-tree/
    // Time: O(N + E)
    // Space: O(N)
    class UnionFind {
        vector<int> id;
        int cnt;
    public:
        UnionFind(int N) : id(N), cnt(N) {
            iota(begin(id), end(id), 0);
        }
        int find(int x) {
            return id[x] == x ? x : (id[x] = find(id[x]));
        }
        void connect(int a, int b) {
            id[find(a)] = find(b);
            --cnt;
        }
        bool connected(int a, int b) {
            return find(a) == find(b);
        }
        int getCount() { return cnt; }
    };
    class Solution {
    public:
        bool validTree(int n, vector<vector<int>>& E) {
            UnionFind uf(n);
            for (auto &e : E) {
                if (uf.connected(e[0], e[1])) return false;
                uf.connect(e[0], e[1]);
            }
            return uf.getCount() == 1;
        }
    };
    
  • class Solution:
        def validTree(self, n: int, edges: List[List[int]]) -> bool:
            def find(x):
                if p[x] != x:
                    p[x] = find(p[x])
                return p[x]
    
            p = list(range(n))
            for a, b in edges:
                if find(a) == find(b):
                    return False
                p[find(a)] = find(b)
                n -= 1
            return n == 1
    
    ############
    
    class Solution:
      # @param {int} n an integer
      # @param {int[][]} edges a list of undirected edges
      # @return {boolean} true if it's a valid tree, or false
      def validTree(self, n, edges):
        # Write your code here
    
        def dfs(root, graph, visited, parent):
          visited[root] = 1
          for nbr in graph.get(root, []):
            if nbr == parent:
              continue
            elif visited[nbr] != 0:
              return False
            if not dfs(nbr, graph, visited, root):
              return False
          visited[root] = 2
          self.nodeVisited += 1
          return True
    
        visited = [0 for _ in range(n)]
        graph = {}
        self.nodeVisited = 0
        for edge in edges:
          start, end = edge[0], edge[1]
          graph[start] = graph.get(start, []) + [end]
          graph[end] = graph.get(end, []) + [start]
    
        if dfs(0, graph, visited, -1) and self.nodeVisited == n:
          return True
        else:
          return False
    
    
  • func validTree(n int, edges [][]int) bool {
    	p := make([]int, n)
    	for i := range p {
    		p[i] = i
    	}
    	var find func(x int) int
    	find = func(x int) int {
    		if p[x] != x {
    			p[x] = find(p[x])
    		}
    		return p[x]
    	}
    	for _, e := range edges {
    		a, b := e[0], e[1]
    		if find(a) == find(b) {
    			return false
    		}
    		p[find(a)] = find(b)
    		n--
    	}
    	return n == 1
    }
    
  • /**
     * @param {number} n
     * @param {number[][]} edges
     * @return {boolean}
     */
    var validTree = function (n, edges) {
        let p = new Array(n);
        for (let i = 0; i < n; ++i) {
            p[i] = i;
        }
        function find(x) {
            if (p[x] != x) {
                p[x] = find(p[x]);
            }
            return p[x];
        }
        for (const [a, b] of edges) {
            if (find(a) == find(b)) {
                return false;
            }
            p[find(a)] = find(b);
            --n;
        }
        return n == 1;
    };
    
    

All Problems

All Solutions