forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathyhkee0404.kt
More file actions
48 lines (48 loc) · 1.79 KB
/
yhkee0404.kt
File metadata and controls
48 lines (48 loc) · 1.79 KB
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
class Solution {
/**
* @param n: An integer
* @param edges: a list of undirected edges
* @return: true if it's a valid tree, or false
*/
fun validTree(n: Int, edges: Array<IntArray>): Boolean {
// write your code here
val adj = List(n) {mutableListOf<Int>()} // S(V, E) = O(V + E)
edges.forEach {
adj[it[0]].add(it[1])
adj[it[1]].add(it[0])
}
var t = 0
val tortoiseStack = mutableListOf<MutableList<Int>>(mutableListOf(0, 0, -1))
val hareStack = mutableListOf<MutableList<Int>>(mutableListOf(0, 0, -1))
var tortoise = listOf(-1)
while (! hareStack.isEmpty()) { // T(V, E) = O(V + E)
val hare = hareStack.last()
if (hare[1] == adj[hare[0]].size) {
hareStack.removeLast()
} else if (adj[hare[0]][hare[1]] != hare[2]) {
hareStack.add(mutableListOf(adj[hare[0]][hare[1]], 0, hare[0]))
}
if (hare[1]++ != 0) {
continue
}
if ((t++ and 1) == 1) {
while (! tortoiseStack.isEmpty()) {
tortoise = tortoiseStack.last()
if (tortoise[1] == adj[tortoise[0]].size) {
tortoiseStack.removeLast()
} else if (adj[tortoise[0]][tortoise[1]] != tortoise[2]) {
tortoiseStack.add(mutableListOf(adj[tortoise[0]][tortoise[1]], 0, tortoise[0]))
}
if (tortoise[1]++ != 0) {
continue
}
break
}
}
if (hare[0] == tortoise[0]) {
return false
}
}
return t == n
}
}