You are given a list of lists edges representing an undirected graph. Each list contains (u, v) which means there
is an undirected edge between nodes u and v. Return whether the graph is a collection of trees.
Constraints: n ≤ 100,000 where n is the length of edges
Source Link : https://binarysearch.com/problems/Forest-Detection
Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
import java.util.*;
/**
* Approach: Group all the elements in the form of disjoint set.
* Iterate through all the edges and add keep adding nodes to the DJ .
* If at any instant if we know two nodes of the edge already exists in the set,
* then it means a cycle node is being detected.
* <p>
* One important step to note is in find(a) method,
* parent[a] = find(parent[a]).
* This step avoids time limit exceeded since all the nodes will eventually report
* to the parent.
* <p>
* Time Complexity: O(E)
* Space Complexity: O(N)
**/
class Solution {
public boolean solveUnionFind(int[][] edges) {
int n = 0;
for (int e[] : edges) {
n = Math.max(n, Math.max(e[0], e[1]));
}
parent = new int[n + 1];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
for (int e[] : edges) {
if (union(e[0], e[1])) {
return false;
}
}
return true;
}
int[] parent;
boolean union(int a, int b) {
int x = find(a);
int y = find(b);
if (x == y) {
//Cycle detected.
return true;
}
parent[x] = y;
return false;
}
int find(int a) {
if (parent[a] == a) {
return a;
}
//Assigning parent[a] to the result makes the disjoint set flat.
//All children will report to root node eventually.
parent[a] = find(parent[a]);
return parent[a];
}
//Solution 2:
/**
* Approach: DFS Cycle detection:
* Perform a Dfs on each of the unvisited nodes.
* If no cycles found it means its a tree.
*
* Time Complexity: O(N)
* Space Compexity: O(N)
*
*/
boolean dfs(int i, int parent, Map<Integer, List<Integer>> map, Set<Integer> visited) {
visited.add(i);
for (Integer x : map.getOrDefault(i, new ArrayList<>())) {
if (x.equals(parent)) {
continue;
}
if (visited.contains(x)) {
return true;
}
if (dfs(x, i, map, visited)) {
return true;
}
}
return false;
}
public boolean solveDFS(int[][] edges) {
int max = 0;
Map<Integer, List<Integer>> map = new HashMap<>();
Set<Integer> visited = new HashSet<>();
for (int[] e : edges) {
max = Math.max(max, Math.max(e[0], e[1]));
List<Integer> list = map.getOrDefault(e[0], new ArrayList<>());
list.add(e[1]);
List<Integer> list2 = map.getOrDefault(e[1], new ArrayList<>());
list2.add(e[0]);
map.put(e[0], list);
map.put(e[1], list2);
}
for (int i = 0; i <= max; i++) {
if (!visited.contains(i)) {
if (dfs(i, -1, map, visited)) {
return false;
}
}
}
return true;
}
}