# Share my [25-line DFS], [20-line BFS] and [clean Union-Find] Java solutions

• Check 2 things: 1. whether there is loop 2. whether the number of connected components is 1

DFS

``````public class Solution {
public boolean validTree(int n, int[][] edges) {
int[] visited = new int[n];
for (int[] edge: edges) {
}
if (hasCycle(-1, 0, visited, adjList)) { return false; }  // has cycle
for (int v: visited) { if (v == 0) { return false; } }  // not 1 single connected component
return true;
}

private boolean hasCycle(int pred, int vertex, int[] visited, List<List<Integer>> adjList) {
visited[vertex] = 1;  // current vertex is being visited
for (Integer succ: adjList.get(vertex)) {  // successors of current vertex
if (succ != pred) {  // exclude current vertex's predecessor
if (visited[succ] == 1) { return true; }  // back edge/loop detected!
else if (visited[succ] == 0) {
if (hasCycle(vertex, succ, visited, adjList)) { return true; }
}
}
}
visited[vertex] = 2;
return false;
}
}
``````

BFS

``````public class Solution {
public boolean validTree(int n, int[][] edges) {
int[] visited = new int[n];
for (int[] edge: edges) {
}
Deque<Integer> q = new ArrayDeque<>();
q.addLast(0); visited[0] = 1;  // vertex 0 is in the queue, being visited
while (!q.isEmpty()) {
Integer cur = q.removeFirst();
if (visited[succ] == 1) { return false; }  // loop detected
if (visited[succ] == 0) { q.addLast(succ); visited[succ] = 1; }
}
visited[cur] = 2;  // visit completed
}
for (int v: visited) { if (v == 0) { return false; } }  // # of connected components is not 1
return true;
}
}
``````

Union-Find with path compression and merge by rank

``````public class Solution {

class UnionFind {

int[] parent;
int[] rank;
int count;

UnionFind(int n) {
parent = new int[n];
rank = new int[n];
count = n;  // number of components
for (int i=0; i<n; ++i) { parent[i] = i; }  // initially, each node's parent is itself.
}

int find(int x) {
if (x != parent[x]) {
parent[x] = find(parent[x]);  // find root with path compression
}
return parent[x];
}

boolean union(int x, int y) {
int X = find(x), Y = find(y);
if (X == Y) { return false; }
if (rank[X] > rank[Y]) { parent[Y] = X; }  // tree Y is lower
else if (rank[X] < rank[Y]) { parent[X] = Y; }  // tree X is lower
else {  // same height
parent[Y] = X;
++rank[X];
}
--count;
return true;
}
}

public boolean validTree(int n, int[][] edges) {
UnionFind uf = new UnionFind(n);
for (int[] edge: edges) {
int x = edge[0], y = edge[1];
if (!uf.union(x, y)) { return false; }  // loop detected
}
return uf.count == 1;
}
}``````

• really nice code

• Hi, why we need visited[vertex] = 2?

• thanks.........

• Hi. In order to pass the tests, I don't think we need it. On the other hand, I prefer the states (unvisited, being visited, visited) look like what they actually are after program execution. Consistency is what I'd like to have :)

• thx for your solution ~ really neatly organized !

your profile pic reminded me of "when i was young and 'bold' and strong" lol

• Could you explain how you come up with the way to check cycle? I haven't seen this before. Thanks!

• @jiaodong :anger_right:

• @brookc
Take a look at edge BA here.

Starting from A, since there exists back edge B->A, when traversing DFS path A-->B-->A, A is visited for a second time. Namely, A is visited AT THE SAME TIME it is still in the DFS recursion stack. Loop detected.

• @brookc It's on CLRS(3rd edition) , Chapter 22, Elementary Graph Algorithms, this chapter includes BFS and DFS with three colored states.

• Thanks for the nice code! But I think "visited[vertex] = 2" is not needed

• @genius1wjc yes, you are right. it is not needed. but i think it is also good to set the state correct... anyway, this is just my personal preference.

• @genius1wjc
@mach7
From my point of view, the "visited[vertex] = 2" is needed because, the code is using adjacent matrix to present the undirected graph. Hence there is an A->B if there is a B->A. When you visited A and add B to the queue. If A's status doesn't change, then in next iteration, B will traverse back to A whose status is still 1 and returns false. Error happens.
So I think status changes to 2 is a must.

• @YuaoLiu He has already changed "visited[vertex]" to 1 when he started visiting the vertex, thus changing it again right before the end of visiting the vertex to 2 is not necessary.

• @genius1wjc
Yes, a pred variable is used to prevent the problem I said in DFS but in BFS setting to 2 is still a must.

• @mach7 As for `if (visited[succ] == 1) { return true; } // back edge/loop detected!` in DFS, I tried `visited[succ] == 1` and `visited[succ] >= 1`, all of them work. I am confused what is the difference between ``visited[succ] == 1`and`visited[succ] ==2```. Thanks

• For the BFS solution in this problem, I believe you can do the following thing to avoid setting visited[cur] = 2, :

when visited[succ] == 1, instead of return false, just continue;

we just need to make sure (1) n == edges.length - 1 (check it at the very beginning of the code) and (2) for all the int v in visited, no 0 exist.

The reason is for a tree (1) for n nodes there must be edges.length + 1 edges and (2) if there is a cycle in it, there is no way to connect all n nodes with edges.length+1 edges.
So there you go.

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