0261-graph-valid-tree.java

publicclassSolution {

privateMap<Integer, List<Integer>> adjacencyList = newHashMap<>();

publicbooleanvalidTree(intn, int[][] edges) {
if (n == 0 || n == 1) returntrue;

if (edges.length == 0) returnfalse;

for (varedge : edges) {
varnode1 = edge[0];
varnode2 = edge[1];
adjacencyList.putIfAbsent(node1, newArrayList<>());
adjacencyList.putIfAbsent(node2, newArrayList<>());
adjacencyList.get(node1).add(node2);
adjacencyList.get(node2).add(node1);
 }

Set<Integer> visited = newHashSet<>();

return (
depthFirstSearch(edges[0][0], -1, visited) && visited.size() == n
 );
 }

privatebooleandepthFirstSearch(
intnode,
intprevious,
Set<Integer> visited
 ) {
if (visited.contains(node)) returnfalse;

visited.add(node);

for (varneighbor : adjacencyList.get(node)) {
if (neighbor == previous) continue;

if (!depthFirstSearch(neighbor, node, visited)) returnfalse;
 }

returntrue;
 }
}