FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
leetcode-algorithms/src/GraphValidTree.java at master · anishLearnsToCode/leetcode-algorithms · GitHub
anishLearnsToCode
/
leetcode-algorithms
Public
Notifications
You must be signed in to change notification settings
Fork
17
Star
98
Code
Issues
0
Pull requests
0
Discussions
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Discussions
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
leetcode-algorithms
/
src
/
GraphValidTree.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
59 lines (52 loc) · 1.54 KB
Breadcrumbs
leetcode-algorithms
/
src
/
GraphValidTree.java
Copy path
File metadata and controls
59 lines (52 loc) · 1.54 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
// https://leetcode.com/problems/graph-valid-tree
// T: O(N)
// S: O(N)
public
class
GraphValidTree
{
private
static
final
class
DisjointSet
{
private
final
int
[]
root
,
rank
;
public
DisjointSet
(
int
size
) {
root
=
new
int
[
size
];
rank
=
new
int
[
size
];
for
(
int
i
=
0
;
i
<
size
;
i
++) {
root
[
i
] =
i
;
rank
[
i
] =
1
;
}
}
public
int
find
(
int
num
) {
if
(
root
[
num
] ==
num
) {
return
num
;
}
return
root
[
num
] =
find
(
root
[
num
]);
}
public
boolean
areConnected
(
int
x
,
int
y
) {
return
find
(
x
) ==
find
(
y
);
}
public
void
union
(
int
x
,
int
y
) {
final
int
rootX
=
find
(
x
),
rootY
=
find
(
y
);
if
(
rootX
==
rootY
) {
return
;
}
if
(
rank
[
rootX
] <
rank
[
rootY
]) {
root
[
rootX
] =
rootY
;
}
else
if
(
rank
[
rootX
] >
rank
[
rootY
]) {
root
[
rootY
] =
rootX
;
}
else
{
root
[
rootY
] =
rootX
;
rank
[
rootX
]++;
}
}
}
public
boolean
validTree
(
int
n
,
int
[][]
edges
) {
if
(
edges
.
length
!=
n
-
1
) {
return
false
;
}
final
DisjointSet
disjointSet
=
new
DisjointSet
(
n
);
for
(
int
[]
edge
:
edges
) {
if
(
disjointSet
.
areConnected
(
edge
[
0
],
edge
[
1
])) {
return
false
;
}
disjointSet
.
union
(
edge
[
0
],
edge
[
1
]);
}
return
true
;
}
}
Back
|
FazBrowse Home
|
New Git URL