Skip to content

Commit 6d5cac2

Browse files
committed
1971-find-if-path-exists-in-graph-2.md Added Java, C++, JavaScript, C#, Go, Ruby UnionFind solutions.
1 parent 009f473 commit 6d5cac2

2 files changed

Lines changed: 223 additions & 10 deletions

File tree

README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -70,6 +70,6 @@ You can skip the more difficult problems and do them later.
7070
- [695. Max Area of Island](solutions/1-1000/695-max-area-of-island.md) was solved in _Python, Java, C++, JavaScript, C#, Go, Ruby_.
7171
- [827. Making A Large Island](solutions/1-1000/827-making-a-large-island.md) was solved in _Python_.
7272
- [127. Word Ladder](solutions/1-1000/127-word-ladder.md) was solved in _Python_.
73-
- [1971. Find if Path Exists in Graph](solutions/1001-2000/1971-find-if-path-exists-in-graph.md) was solved in _Python_.
73+
- [1971. Find if Path Exists in Graph](solutions/1001-2000/1971-find-if-path-exists-in-graph.md) was solved in _Python, Java, C++, JavaScript, C#, Go, Ruby_ and 2 solutions.
7474

7575
More LeetCode problems will be added soon...

solutions/1001-2000/1971-find-if-path-exists-in-graph-2.md

Lines changed: 222 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -50,7 +50,7 @@ And this graph may have multiple **connected components**. Initially, we start f
5050

5151
- We need to find if there is a path from `source` to `destination`. This question is equivalent to determine if `source` and `destination` vertices belong to the same `connected component`.
5252
- A `tree` is a type of `graph`. If two nodes are in the same tree, then return `true`. So we need a method `in_same_tree(node1, node2)` to return a boolean value.
53-
- We are `edges` data and need to divide them into multiple groups, each group can be abstracted into a **tree**.
53+
- We are given `edges` data and need to divide them into multiple groups, each group can be abstracted into a **tree**.
5454
- `UnionFind` algorithm is designed for grouping and searching data.
5555

5656
### 'UnionFind' algorithm
@@ -60,12 +60,12 @@ And this graph may have multiple **connected components**. Initially, we start f
6060
- The `same_root(node1, node2)` method can be used to judge if two nodes are in the same tree.
6161

6262
## Approach (UnionFind algorithm)
63-
1. Initially, every node is in the group of itself.
63+
1. Initially, each node is in its own group.
6464
1. Iterate `edges` data and `unite(node1, node2)`.
6565
1. Return `same_root(source, destination)`.
6666

6767
## Complexity
68-
* Time: `O(n)`.
68+
* Time: `O(n)`.
6969
* Space: `O(n)`.
7070

7171
## Python
@@ -144,32 +144,245 @@ class Solution:
144144

145145
## Java
146146
```java
147-
// Welcome to create a PR to complete the code of this language, thanks!
147+
class Solution {
148+
private int[] father;
149+
150+
public boolean validPath(int n, int[][] edges, int source, int destination) {
151+
father = new int[n];
152+
153+
for (var i = 0; i < n; i++) {
154+
father[i] = i;
155+
}
156+
157+
for (var edge : edges) {
158+
unite(edge[0], edge[1]);
159+
}
160+
161+
return sameRoot(source, destination);
162+
}
163+
164+
private void unite(int x, int y) {
165+
int rootX = findRoot(x);
166+
int rootY = findRoot(y);
167+
168+
father[rootY] = rootX; // Error-prone point 1
169+
}
170+
171+
private int findRoot(int x) {
172+
if (x == father[x]) {
173+
return x;
174+
}
175+
176+
father[x] = findRoot(father[x]); // Error-prone point 2
177+
178+
return father[x];
179+
}
180+
181+
private boolean sameRoot(int x, int y) {
182+
return findRoot(x) == findRoot(y);
183+
}
184+
}
148185
```
149186

150187
## C++
151188
```cpp
152-
// Welcome to create a PR to complete the code of this language, thanks!
189+
class Solution {
190+
private:
191+
vector<int> father;
192+
193+
void unite(int x, int y) {
194+
int root_x = findRoot(x);
195+
int root_y = findRoot(y);
196+
197+
father[root_y] = root_x; // Error-prone point 1
198+
}
199+
200+
int findRoot(int x) {
201+
if (x == father[x]) {
202+
return x;
203+
}
204+
205+
father[x] = findRoot(father[x]); // Error-prone point 2
206+
207+
return father[x];
208+
}
209+
210+
bool sameRoot(int x, int y) {
211+
return findRoot(x) == findRoot(y);
212+
}
213+
214+
public:
215+
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
216+
for (auto i = 0; i < n; i++) {
217+
father.push_back(i);
218+
}
219+
220+
for (auto& edge : edges) {
221+
unite(edge[0], edge[1]);
222+
}
223+
224+
return sameRoot(source, destination);
225+
}
226+
};
153227
```
154228
155229
## JavaScript
156230
```javascript
157-
// Welcome to create a PR to complete the code of this language, thanks!
231+
let father
232+
233+
var validPath = function (n, edges, source, destination) {
234+
father = []
235+
for (let i = 0; i < n; i++) {
236+
father.push(i)
237+
}
238+
239+
for (let [a, b] of edges) {
240+
unite(a, b)
241+
}
242+
243+
return sameRoot(source, destination)
244+
};
245+
246+
function unite(x, y) {
247+
rootX = findRoot(x)
248+
rootY = findRoot(y)
249+
250+
father[rootY] = rootX // Error-prone point 1
251+
}
252+
253+
function findRoot(x) {
254+
if (x == father[x]) {
255+
return x
256+
}
257+
258+
father[x] = findRoot(father[x]) // Error-prone point 2
259+
260+
return father[x]
261+
}
262+
263+
function sameRoot(x, y) {
264+
return findRoot(x) == findRoot(y)
265+
}
158266
```
159267

160268
## C#
161269
```c#
162-
// Welcome to create a PR to complete the code of this language, thanks!
270+
public class Solution
271+
{
272+
int[] father;
273+
274+
public bool ValidPath(int n, int[][] edges, int source, int destination)
275+
{
276+
father = new int[n];
277+
278+
for (int i = 0; i < n; i++)
279+
father[i] = i;
280+
281+
foreach (int[] edge in edges)
282+
{
283+
unite(edge[0], edge[1]);
284+
}
285+
286+
return sameRoot(source, destination);
287+
}
288+
289+
void unite(int x, int y)
290+
{
291+
int rootX = findRoot(x);
292+
int rootY = findRoot(y);
293+
294+
father[rootY] = rootX; // Error-prone point 1
295+
}
296+
297+
int findRoot(int x)
298+
{
299+
if (x == father[x])
300+
return x;
301+
302+
father[x] = findRoot(father[x]); // Error-prone point 2
303+
304+
return father[x];
305+
}
306+
307+
bool sameRoot(int x, int y)
308+
{
309+
return findRoot(x) == findRoot(y);
310+
}
311+
}
163312
```
164313

165314
## Go
166315
```go
167-
// Welcome to create a PR to complete the code of this language, thanks!
316+
var father []int
317+
318+
func validPath(n int, edges [][]int, source int, destination int) bool {
319+
father = make([]int, n)
320+
for i := 0; i < n; i++ {
321+
father[i] = i
322+
}
323+
324+
for _, edge := range edges {
325+
unite(edge[0], edge[1])
326+
}
327+
328+
return sameRoot(source, destination)
329+
}
330+
331+
func unite(x, y int) {
332+
rootX := findRoot(x)
333+
rootY := findRoot(y)
334+
335+
father[rootY] = rootX // Error-prone point 1
336+
}
337+
338+
func findRoot(x int) int {
339+
if x == father[x] {
340+
return x
341+
}
342+
343+
father[x] = findRoot(father[x]) // Error-prone point 2
344+
345+
return father[x]
346+
}
347+
348+
func sameRoot(x, y int) bool {
349+
return findRoot(x) == findRoot(y)
350+
}
168351
```
169352

170353
## Ruby
171354
```ruby
172-
# Welcome to create a PR to complete the code of this language, thanks!
355+
def valid_path(n, edges, source, destination)
356+
@father = []
357+
(0...n).each { |i| @father << i }
358+
359+
edges.each do |edge|
360+
unite(edge[0], edge[1])
361+
end
362+
363+
same_root(source, destination)
364+
end
365+
366+
def unite(x, y)
367+
root_x = find_root(x)
368+
root_y = find_root(y)
369+
370+
@father[root_y] = root_x # Error-prone point 1
371+
end
372+
373+
def find_root(x)
374+
if x == @father[x]
375+
return x
376+
end
377+
378+
@father[x] = find_root(@father[x]) # Error-prone point 2
379+
380+
@father[x]
381+
end
382+
383+
def same_root(x, y)
384+
find_root(x) == find_root(y)
385+
end
173386
```
174387

175388
## C

0 commit comments

Comments
 (0)