public class Solution {
public boolean validTree(int n, int[][] edges) {
// initialize adjacency list
List<List<Integer>> adjList = new ArrayList<List<Integer>>(n);
// initialize vertices
for (int i = 0; i < n; i++)
adjList.add(i, new ArrayList<Integer>());
// add edges
for (int i = 0; i < edges.length; i++) {
int u = edges[i][0], v = edges[i][1];
adjList.get(u).add(v);
adjList.get(v).add(u);
}
boolean[] visited = new boolean[n];
// make sure there's no cycle
if (hasCycle(adjList, 0, visited, 1))
return false;
// make sure all vertices are connected
for (int i = 0; i < n; i++) {
if (!visited[i])
return false;
}
return true;
}
// check if an undirected graph has cycle started from vertex u
boolean hasCycle(List<List<Integer>> adjList, int u, boolean[] visited, int parent) {
visited[u] = true;
for (int i = 0; i < adjList.get(u).size(); i++) {
int v = adjList.get(u).get(i);
if ((visited[v] && parent != v)  (!visited[v] && hasCycle(adjList, v, visited, u)))
return true;
}
return false;
}
}
AC Java Graph DFS solution with adjacency list



You could probably do away with the check for visited by filling a set with 0 to n1 as you are creating the adjacency list and then removing each one you visit as you check for a cycle. If the set isn't empty after the check then something was missed. Not an asymptotic difference but just one less O(n) traversal over the list.

@jeantimex Hi, I think you just need do a normal dfs from any node, and do the visit check after that. The tree validation could be guaranteed by checking
 # of nodes == # of edges + 1
 No self loop


@TōsakaRin I am confused by that too. So I used the same thoughts but made it more easily understand.
public class Solution { public boolean validTree(int n, int[][] edges) { List<List<Integer>> graph = new ArrayList<>(); for (int i = 0; i < n; i++) { graph.add(new ArrayList<Integer>()); } // initialize adjacency list. for (int i = 0; i < edges.length; i++) { graph.get(edges[i][0]).add(edges[i][1]); graph.get(edges[i][1]).add(edges[i][0]); } Set<Integer> visited = new HashSet<>(); visited.add(0); // do DFS from vertex 0, after one round DFS, if there is no loop and visited contains all the vertexs, // it is a tree. boolean res = helper(1, 0, visited, graph); if (!res) return res; return visited.size() == n ? true : false; } public boolean helper(int parent, int vertex, Set<Integer> visited, List<List<Integer>> graph) { List<Integer> subs = graph.get(vertex); for (int v : subs) { // if v is vertex's parent, continue. if (v == parent) continue; // if v is not vertex's parent, and v is visited. that presents there is a cycle in this graph. if(visited.contains(v)) return false; visited.add(v); boolean res = helper(vertex, v, visited, graph); if (!res) return false; } return true; } }

