Question

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

 261	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 in edges.

 @tag-graph

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

Java

  • 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;
            }
        }
    }
    
  • // 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:
      # @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
    
    

All Problems

All Solutions