# My AC Answers: Union Find, BFS, DFS

• ``````// Union Find

public class Solution {
public boolean validTree(int n, int[][] edges) {
if(n < 1 || edges == null){
return false;
}
int[] uf = new int[n];
for(int i = 0; i < n; i++){
uf[i] = i;
}
for(int i = 0; i < edges.length; i++){
if(union(uf,edges[i][0],edges[i][1]) == false){
return false;
}
}
int count = 0;
for(int i = 0; i < n; i++){
if(uf[i] == i){
count++;
}
}
return count == 1;
}

public int find(int[] uf, int target){
int rst = target;
while(uf[rst] != rst){
rst = uf[rst];
}
// compress
int next = uf[target];
while(next != rst){
uf[target] = rst;
target = next;
next = uf[next];
}
return rst;
}

public boolean union(int[] uf, int f1, int f2){
int p1 = find(uf,f1);
int p2 = find(uf,f2);
if(p1 == p2){
return false;
}
else{
uf[p1] = p2;
}
return true;
}

}

// BFS

public class Solution {
public boolean validTree(int n, int[][] edges) {
if(n < 1 || edges == null){
return false;
}
ArrayList<Integer>[] edgeList = new ArrayList[n];
for(int i = 0; i < n; i++){
edgeList[i] = new ArrayList();
}
for(int[] edge : edges){
}
boolean[] visited = new boolean[n];

queue.offer(0);
while(!queue.isEmpty()){
int top = queue.poll();
if(visited[top]){
return false;
}
visited[top] = true;
for(int next : edgeList[top]){
if(!visited[next]){
queue.offer(next);
}
}
}
for(boolean bl : visited){
if(!bl){
return false;
}
}

return true;
}
}

// DFS

public class Solution {
public boolean validTree(int n, int[][] edges) {
if(n < 1 || edges == null){
return false;
}
ArrayList<Integer>[] edgeList = new ArrayList[n];
for(int i = 0; i < n; i++){
edgeList[i] = new ArrayList();
}
for(int[] edge : edges){
}
boolean[] visited = new boolean[n];
if(dfs(edgeList,visited,0,0) == false){
return false;
}
for(boolean bl : visited){
if(!bl){
return false;
}
}
return true;
}

public boolean dfs(ArrayList<Integer>[] edgeList,boolean[] visited, int target,int father){
if(visited[target]){
return false;
}
visited[target] = true;
for(int next : edgeList[target]){
if(next != father){
if(dfs(edgeList,visited,next,target) == false){
return false;
}
}
}
return true;
}
}

``````

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