-
Notifications
You must be signed in to change notification settings - Fork 0
/
validPath.ts
53 lines (46 loc) · 1.35 KB
/
validPath.ts
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
export default function validPath(
n: number,
edges: number[][],
source: number,
destination: number,
): boolean {
if (source === destination) return true;
if (edges.length === 0) return false;
const nodes = new Set(Array(n).keys());
const edge: Set<number>[] = Array(n)
.fill(0)
.map(() => new Set());
for (const [a, b] of edges) {
edge[a].add(b);
edge[b].add(a);
}
if (!nodes.has(destination) || !nodes.has(source)) return false;
let current = new Set([source]);
let rightcurrent = new Set([destination]);
nodes.delete(destination);
nodes.delete(source);
let step = 1;
while (current.size) {
if (current.size > rightcurrent.size) {
[current, rightcurrent] = [rightcurrent, current];
}
const temp: Set<number> = new Set();
for (const word of current) {
for (const right of rightcurrent) {
if (edge[word].has(right)) {
return true;
}
}
for (const other of nodes) {
if (edge[other].has(word)) {
temp.add(other);
nodes.delete(other);
}
}
}
if (temp.size === 0) return false;
current = temp;
step = step + 1;
}
return false;
}