# AC Java Graph DFS solution with adjacency list

• public class Solution {
public boolean validTree(int n, int[][] edges) {

// initialize vertices
for (int i = 0; i < n; i++)

for (int i = 0; i < edges.length; i++) {
int u = edges[i][0], v = edges[i][1];
}

boolean[] visited = new boolean[n];

// make sure there's no cycle
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++) {

if ((visited[v] && parent != v) || (!visited[v] && hasCycle(adjList, v, visited, u)))
return true;
}

return false;
}
}

• the hasCycle method can be made to a tail recursion.

• @HoSi Could you please explain the details?

• Java isn't optimized for tail recursion so it wouldn't give any benefit. Good thinking, though. :)

• You could probably do away with the check for visited by filling a set with 0 to n-1 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.

• I think you can avoid the loop at:
// make sure all vertices are connected
by maintaining count of total visited vertices and comparing it to the total number of vertices at the end

• @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

1. # of nodes == # of edges + 1
2. No self loop

• parent is really good idea.

• Same idea, but I think List[] is adequate to construct adjacent list. Thanks for sharing!

• Can anyone explain some about (visited[v] && parent != v) || (!visited[v] && hasCycle(adjList, v, visited, u) ?

• Can anyone help me to figure out the time complexity of this method? Thx!

• @huksy.li
I think it's O( |E| + |V| )

• @mycoy thanks!

• @Tōsaka-Rin 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++) {
}

for (int i = 0; i < edges.length; i++) {
}
Set<Integer> visited = new HashSet<>();

// 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;
boolean res = helper(vertex, v, visited, graph);
if (!res) return false;
}
return true;
}
}

• @jilianggqq Your solution is much easier to understand. Thanks.

• @jilianggqq In fact, I think use "pre" instead of "parent" should be better.

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