Java Concise DFS


  • 0
    public class Solution {
        public boolean validTree(int n, int[][] edges) {
            if (edges == null || edges.length == 0 || edges[0].length == 0) return n == 1;
            if (edges.length >= n) return false;
            Map<Integer, Set<Integer>> map = new HashMap<>();
            for (int i = 0; i < n; i++) map.put(i, new HashSet<>());
            for (int[] edge : edges) {
                map.get(edge[0]).add(edge[1]);
                map.get(edge[1]).add(edge[0]);
            }
            Set<Integer> visited = new HashSet<>();
            dfs(edges[0][0], visited, map);
            return visited.size() == n;
        }
        private void dfs(int curr, Set<Integer> visited, Map<Integer, Set<Integer>> map) {
            if (!visited.add(curr)) return;
            for (int child : map.get(curr)) {
                dfs(child, visited, map);
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.