Skip to content

Commit 2689bea

Browse files
gazeldxgazeldx
committed
1971-find-if-path-exists-in-graph-2.md Perfected code.
1 parent fc51fb8 commit 2689bea

File tree

2 files changed

+181
-133
lines changed

2 files changed

+181
-133
lines changed

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

+88-64
Original file line numberDiff line numberDiff line change
@@ -54,12 +54,12 @@ This graph may have multiple **connected components**.
5454
- `UnionFind` algorithm typically has three methods:
5555
- The `unite(node1, node2)` operation can be used to merge two trees.
5656
- The `find_root(node)` method can be used to return the root of a node.
57-
- The `same_root(node1, node2)` method is used to determine whether two nodes are in the same tree.
57+
- The `is_same_root(node1, node2)` method is used to determine whether two nodes are in the same tree.
5858

5959
## Approach (UnionFind algorithm)
6060
1. Initially, each node is in its own group.
6161
1. Iterate `edges` data and `unite(node1, node2)`.
62-
1. Return `same_root(source, destination)`.
62+
1. Return `is_same_root(source, destination)`.
6363

6464
## Complexity
6565
* Time: `O(n)`.
@@ -69,32 +69,33 @@ This graph may have multiple **connected components**.
6969
### Standard UnionFind algorithm (recommended)
7070
```python
7171
class Solution:
72-
def __init__(self):
73-
self.parent = None
74-
7572
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
76-
self.parent = list(range(n))
73+
self.parents = list(range(n))
7774

7875
for x, y in edges:
7976
self.unite(x, y)
8077

81-
return self.same_root(source, destination)
78+
return self.is_same_root(source, destination)
8279

8380
def unite(self, x, y):
8481
root_x = self.find_root(x)
8582
root_y = self.find_root(y)
8683

87-
self.parent[root_y] = root_x # Error-prone point 1
84+
self.parents[root_y] = root_x # Error-prone point 1
8885

8986
def find_root(self, x):
90-
if x == self.parent[x]:
87+
parent = self.parents[x]
88+
89+
if x == parent:
9190
return x
9291

93-
self.parent[x] = self.find_root(self.parent[x]) # Error-prone point 2
92+
root = self.find_root(parent) # Error-prone point 2
93+
94+
self.parents[x] = root # Error-prone point 3
9495

95-
return self.parent[x]
96+
return root
9697

97-
def same_root(self, x, y):
98+
def is_same_root(self, x, y):
9899
return self.find_root(x) == self.find_root(y)
99100
```
100101

@@ -145,40 +146,44 @@ class Solution:
145146
## Java
146147
```java
147148
class Solution {
148-
private int[] parent;
149+
private int[] parents;
149150

150151
public boolean validPath(int n, int[][] edges, int source, int destination) {
151-
parent = new int[n];
152+
parents = new int[n];
152153

153154
for (var i = 0; i < n; i++) {
154-
parent[i] = i;
155+
parents[i] = i;
155156
}
156157

157158
for (var edge : edges) {
158159
unite(edge[0], edge[1]);
159160
}
160161

161-
return sameRoot(source, destination);
162+
return isSameRoot(source, destination);
162163
}
163164

164165
private void unite(int x, int y) {
165166
int rootX = findRoot(x);
166167
int rootY = findRoot(y);
167168

168-
parent[rootY] = rootX; // Error-prone point 1
169+
parents[rootY] = rootX; // Error-prone point 1
169170
}
170171

171172
private int findRoot(int x) {
172-
if (x == parent[x]) {
173+
var parent = parents[x];
174+
175+
if (x == parent) {
173176
return x;
174177
}
175178

176-
parent[x] = findRoot(parent[x]); // Error-prone point 2
179+
var root = findRoot(parent); // Error-prone point 2
180+
181+
parents[x] = root; // Error-prone point 3
177182

178-
return parent[x];
183+
return root;
179184
}
180185

181-
private boolean sameRoot(int x, int y) {
186+
private boolean isSameRoot(int x, int y) {
182187
return findRoot(x) == findRoot(y);
183188
}
184189
}
@@ -190,77 +195,85 @@ class Solution {
190195
public:
191196
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
192197
for (auto i = 0; i < n; i++) {
193-
parent.push_back(i);
198+
parents.push_back(i);
194199
}
195200

196201
for (auto& edge : edges) {
197202
unite(edge[0], edge[1]);
198203
}
199204

200-
return sameRoot(source, destination);
205+
return isSameRoot(source, destination);
201206
}
202207

203208
private:
204-
vector<int> parent;
209+
vector<int> parents;
205210

206211
void unite(int x, int y) {
207212
int root_x = findRoot(x);
208213
int root_y = findRoot(y);
209214

210-
parent[root_y] = root_x; // Error-prone point 1
215+
parents[root_y] = root_x; // Error-prone point 1
211216
}
212217

213218
int findRoot(int x) {
214-
if (x == parent[x]) {
219+
auto parent = parents[x];
220+
221+
if (x == parent) {
215222
return x;
216223
}
217224

218-
parent[x] = findRoot(parent[x]); // Error-prone point 2
225+
auto root = findRoot(parent); // Error-prone point 2
226+
227+
parents[x] = root; // Error-prone point 3
219228

220-
return parent[x];
229+
return root;
221230
}
222231

223-
bool sameRoot(int x, int y) {
232+
bool isSameRoot(int x, int y) {
224233
return findRoot(x) == findRoot(y);
225234
}
226235
};
227236
```
228237
229238
## JavaScript
230239
```javascript
231-
let parent
240+
let parents
232241
233242
var validPath = function (n, edges, source, destination) {
234-
parent = []
243+
parents = []
235244
for (let i = 0; i < n; i++) {
236-
parent.push(i)
245+
parents.push(i)
237246
}
238247
239248
for (const [a, b] of edges) {
240249
unite(a, b)
241250
}
242251
243-
return sameRoot(source, destination)
252+
return isSameRoot(source, destination)
244253
};
245254
246255
function unite(x, y) {
247256
rootX = findRoot(x)
248257
rootY = findRoot(y)
249258
250-
parent[rootY] = rootX // Error-prone point 1
259+
parents[rootY] = rootX // Error-prone point 1
251260
}
252261
253262
function findRoot(x) {
254-
if (x == parent[x]) {
263+
const parent = parents[x]
264+
265+
if (x == parent) {
255266
return x
256267
}
257268
258-
parent[x] = findRoot(parent[x]) // Error-prone point 2
269+
const root = findRoot(parent) // Error-prone point 2
270+
271+
parents[x] = root // Error-prone point 3
259272
260-
return parent[x]
273+
return root
261274
}
262275
263-
function sameRoot(x, y) {
276+
function isSameRoot(x, y) {
264277
return findRoot(x) == findRoot(y)
265278
}
266279
```
@@ -269,42 +282,46 @@ function sameRoot(x, y) {
269282
```c#
270283
public class Solution
271284
{
272-
int[] parent;
285+
int[] parents;
273286

274287
public bool ValidPath(int n, int[][] edges, int source, int destination)
275288
{
276-
parent = new int[n];
289+
parents = new int[n];
277290

278291
for (int i = 0; i < n; i++)
279-
parent[i] = i;
292+
parents[i] = i;
280293

281294
foreach (int[] edge in edges)
282295
{
283296
unite(edge[0], edge[1]);
284297
}
285298

286-
return sameRoot(source, destination);
299+
return isSameRoot(source, destination);
287300
}
288301

289302
void unite(int x, int y)
290303
{
291304
int rootX = findRoot(x);
292305
int rootY = findRoot(y);
293306

294-
parent[rootY] = rootX; // Error-prone point 1
307+
parents[rootY] = rootX; // Error-prone point 1
295308
}
296309

297310
int findRoot(int x)
298311
{
299-
if (x == parent[x])
312+
int parent = parents[x];
313+
314+
if (x == parent)
300315
return x;
301316

302-
parent[x] = findRoot(parent[x]); // Error-prone point 2
317+
int root = findRoot(parent); // Error-prone point 2
318+
319+
parents[x] = root; // Error-prone point 3
303320
304-
return parent[x];
321+
return root;
305322
}
306323

307-
bool sameRoot(int x, int y)
324+
bool isSameRoot(int x, int y)
308325
{
309326
return findRoot(x) == findRoot(y);
310327
}
@@ -313,74 +330,81 @@ public class Solution
313330

314331
## Go
315332
```go
316-
var parent []int
333+
var parents []int
317334

318335
func validPath(n int, edges [][]int, source int, destination int) bool {
319-
parent = make([]int, n)
336+
parents = make([]int, n)
320337
for i := 0; i < n; i++ {
321-
parent[i] = i
338+
parents[i] = i
322339
}
323340

324341
for _, edge := range edges {
325342
unite(edge[0], edge[1])
326343
}
327344

328-
return sameRoot(source, destination)
345+
return isSameRoot(source, destination)
329346
}
330347

331348
func unite(x, y int) {
332349
rootX := findRoot(x)
333350
rootY := findRoot(y)
334351

335-
parent[rootY] = rootX // Error-prone point 1
352+
parents[rootY] = rootX // Error-prone point 1
336353
}
337354

338355
func findRoot(x int) int {
339-
if x == parent[x] {
356+
parent := parents[x];
357+
358+
if x == parent {
340359
return x
341360
}
342361

343-
parent[x] = findRoot(parent[x]) // Error-prone point 2
362+
root := findRoot(parent) // Error-prone point 2
363+
364+
parents[x] = root // Error-prone point 3
344365

345-
return parent[x]
366+
return root
346367
}
347368

348-
func sameRoot(x, y int) bool {
369+
func isSameRoot(x, y int) bool {
349370
return findRoot(x) == findRoot(y)
350371
}
351372
```
352373

353374
## Ruby
354375
```ruby
355376
def valid_path(n, edges, source, destination)
356-
@parent = []
357-
(0...n).each { |i| @parent << i }
377+
@parents = (0...n).to_a
358378

359379
edges.each do |edge|
360380
unite(edge[0], edge[1])
361381
end
362382

363-
same_root(source, destination)
383+
is_same_root(source, destination)
364384
end
365385

366386
def unite(x, y)
367387
root_x = find_root(x)
368388
root_y = find_root(y)
369389

370-
@parent[root_y] = root_x # Error-prone point 1
390+
@parents[root_y] = root_x # Error-prone point 1
371391
end
372392

373393
def find_root(x)
374-
if x == @parent[x]
394+
parent = @parents[x]
395+
396+
if x == parent
375397
return x
376398
end
377399

378-
@parent[x] = find_root(@parent[x]) # Error-prone point 2
400+
root = find_root(parent) # Error-prone point 2
401+
402+
@parents[x] = root # Error-prone point 3
379403

380-
@parent[x]
404+
root
381405
end
382406

383-
def same_root(x, y)
407+
def is_same_root(x, y)
384408
find_root(x) == find_root(y)
385409
end
386410
```

0 commit comments

Comments
 (0)