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

All Problems

All Solutions