# 261 Graph Valid Tree

## 1. Question

Given`n`nodes labeled from`0`to`n - 1`and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given`n = 5`and`edges = [[0, 1], [0, 2], [0, 3], [1, 4]]`, return`true`.

Given`n = 5`and`edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]`, return`false`.

Note: you can assume that no duplicate edges will appear in`edges`. Since all edges are undirected,`[0, 1]`is the same as`[1, 0]`and thus will not appear together in`edges`.

## 2. Implementation

(1) BFS

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

for (int i = 0; i < n; i++) {
}

for (int[] edge : edges) {
}

boolean[] visited = new boolean[n];

while (!queue.isEmpty()) {
int curNode = queue.remove();

// found loop
if (visited[curNode]) {
return false;
}

visited[curNode] = true;

for (int nextNode : adjList.get(curNode)) {
}
}

for (boolean e : visited) {
if (!e) {
return false;
}
}
return true;
}
}``````

(2) DFS

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

for (int i = 0; i < n; i++) {
}

for (int[] edge : edges) {
}

boolean[] visited = new boolean[n];

// Check if graph has cycle
if (hasCycle(0, visited, adjList, -1)) {
return false;
}

// Check if graph is connected
for (int i = 0; i < n; i++) {
if (!visited[i]) {
return false;
}
}
return true;
}

public boolean hasCycle(int node, boolean[] visited, List<Set<Integer>> adjList, int parent) {
visited[node] = true;

for (int nextNode : adjList.get(node)) {
// (1) If nextNode is visited but it is not the parent of the curNode, then there is cycle
// (2) If nextNode is not visited but we still find the cycle later on, return true;
if ((visited[nextNode] && parent != nextNode) || (!visited[nextNode] && hasCycle(nextNode, visited, adjList, node))) {
return true;
}
}
return false;
}
}``````

(3) Union Find

``````class Solution {
public boolean validTree(int n, int[][] edges) {
UnionFind uf = new UnionFind(n);

for (int[] edge : edges) {
// Find Loop
if (!uf.union(edge[0], edge[1])) {
return false;
}
}
// Make sure the graph is connected
return uf.count == 1;
}

class UnionFind {
int[] sets;
int[] size;
int count;

public UnionFind(int n) {
sets = new int[n];
size = new int[n];
count = n;

for (int i = 0; i < n; i++) {
sets[i] = i;
size[i] = 1;
}
}

public int find(int node) {
while (node != sets[node]) {
node = sets[node];
}
return node;
}

public boolean union(int i, int j) {
int node1 = find(i);
int node2 = find(j);

if (node1 == node2) {
return false;
}

if (size[node1] < size[node2]) {
sets[node1] = node2;
size[node2] += size[node1];
}
else {
sets[node2] = node1;
size[node1] += size[node2];
}
--count;
return true;
}
}
}``````

## 3. Time & Space Complexity

BFS: 时间复杂度O(n), 空间复杂度O(n)

DFS: 时间复杂度O(n), 空间复杂度O(n)

Union Find: 时间复杂度O(n), 空间复杂度O(n)

Last updated