AC Java solutions: Union-Find, BFS, DFS

• ``````class Node{
int val;
Node parent;
public Node(int val)
{
this.val = val;
}
}

public class Solution {
Map<Integer, Node> forest;

public boolean validTree(int n, int[][] edges) {
return unionFind(n, edges);
}

private boolean unionFind(int n, int[][] edges)
{
// make set for each node
forest = new HashMap<Integer, Node>();
for(int i = 0; i < n; i++)
forest.put(i, makeSet(i));

// for the two vertice of each edge, find if they are in the same set,
// If so, there is a cycle, return false.
for(int[] edge : edges)
{
if(find(edge[0]) == find(edge[1]))
return false;

union(edge[0], edge[1]);
}

return edges.length == n - 1;
}

private Node makeSet(int val)
{
Node node = new Node(val);
node.parent = node;
return node;
}

private Node find(int node)
{
if(forest.get(node).parent.val == node)
return forest.get(node);

return find(forest.get(node).parent.val);
}

private void union(int node1, int node2)
{
Node set1 = find(node1);
Node set2 = find(node2);
set1.parent = set2;
}

// DFS, using stack
private boolean validDFS(int n, int[][] edges)
{
// build the graph using adjacent list
List<Set<Integer>> graph = new ArrayList<Set<Integer>>();
for(int i = 0; i < n; i++)
for(int[] edge : edges)
{
}

// no cycle
boolean[] visited = new boolean[n];
Deque<Integer> stack = new ArrayDeque<Integer>();
stack.push(0);
while(!stack.isEmpty())
{
int node = stack.pop();
if(visited[node])
return false;
visited[node] = true;
for(int neighbor : graph.get(node))
{
stack.push(neighbor);
graph.get(neighbor).remove(node);
}
}

// fully connected
for(boolean result : visited)
{
if(!result)
return false;
}

return true;
}

// BFS, using queue
private boolean valid(int n, int[][] edges)
{
// build the graph using adjacent list
List<Set<Integer>> graph = new ArrayList<Set<Integer>>();
for(int i = 0; i < n; i++)
for(int[] edge : edges)
{
}

// no cycle
boolean[] visited = new boolean[n];
Queue<Integer> queue = new ArrayDeque<Integer>();
while(!queue.isEmpty())
{
int node = queue.poll();
if(visited[node])
return false;
visited[node] = true;
for(int neighbor : graph.get(node))
{
queue.offer(neighbor);
graph.get(neighbor).remove((Integer)node);
}
}

// fully connected
for(boolean result : visited)
{
if(!result)
return false;
}

return true;
}
}``````

• In the BFS one, while loop can't not detect loop, try{ [1, 2] [2, 3] [1, 3]}:

``````boolean[] visited = new boolean[n];
Queue<Integer> queue = new ArrayDeque<Integer>();
while(!queue.isEmpty())
{
int node = queue.poll();
if(visited[node])
return false;
visited[node] = true;
for(int neighbor : graph.get(node))
{
queue.offer(neighbor);
graph.get(neighbor).remove((Integer)node);
}
}
``````

Should be:

``````boolean[] visited = new boolean[n];
Queue<Integer> queue = new ArrayDeque<Integer>();
while(!queue.isEmpty())
{
int node = queue.poll();
for(int neighbor : graph.get(node))
{
if(visited[neighbor])
return false;
visited[neighbor] = true;
queue.offer(neighbor);
graph.get(neighbor).remove((Integer)node);
}
}``````

• @zjh08177
seems not true. ran his version with our test case returned false.

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