-
Notifications
You must be signed in to change notification settings - Fork 2
/
longestCycle.js
69 lines (63 loc) · 1.4 KB
/
longestCycle.js
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
60
61
62
63
64
65
66
67
68
69
let test = [1,3,5,2,3,6];
console.log(longestCycle(test, 6));
return;
let fs = require('fs');
let args = process.argv.slice(2);
if (!args.length) {
console.log("\nUsage: node longestCycle.js [live-edge-file]");
return;
}
let lines = fs.readFileSync(args[0], 'utf8').split('\n');
let data = [],
count = 0,
delim = ',';
lines.forEach(parseLine);
console.log('parsed ' + count + ' lines');
let lrs = longestCycle(data, data.length);
console.log(lrs);
/////////////////////////////////////////////////////////////////////
function longestCycle(arr, N) {
let maxlen = -1;
let visited = new Array(arr.length);
visited.fill(false);
for (let i = 0; i < N; i++) {
if (!visited[i]) {
let len = 0;
dfs(i, arr[i], arr, N, visited, len);
maxlen = Math.max(maxlen, len);
}
}
return maxlen;
}
function dfs(start, idx, arr, N, visited, len) {
if (idx >= N) {
len = 1;
return;
}
visited[idx] = true;
len++;
if (!visited[arr[idx]]) {
dfs(start, arr[idx], arr, N, visited, len);
}
else if (start == idx) {
return;
}
}
function parseLine(l) {
if (!l.startsWith('source,target,med,step')) {
let parts = l.split(',');
if (parts && parts.length == 4) {
data.push(parts[0]);
count++;
}
}
}
function getMatches(s, re, idx) {
let matches = [],
m;
do {
m = re.exec(s);
if (m) matches.push(m[1]);
} while (m);
return matches;
}