-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathstructy-109-tolerantTeams.js
127 lines (99 loc) · 2.82 KB
/
structy-109-tolerantTeams.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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
// https://structy.net/problems/premium/tolerant-teams
// p: arr
// r: boolean
// dfs recursion
const tolerantTeams = (rivalries) => {
const map = {};
const graph = makeGraph(rivalries);
for (const p in graph) {
// if (p in map) continue;
if (!(p in map) && !getTeam(graph, map, p, false)) return false;
}
return true;
};
const getTeam = (graph, map, p, team) => {
if (p in map) return map[p] === team;
map[p] = team;
for (const p2 of graph[p]) {
if (!getTeam(graph, map, p2, !team)) return false;
}
return true;
};
// // dfs iteration
// const tolerantTeams = (rivalries) => {
// const graph = makeGraph(rivalries);
// const map = {};
// for (const p in graph) {
// if (p in map) continue;
// const stack = [[p, false]];
// while (stack.length > 0) {
// const [p1, team] = stack.pop();
// if (p1 in map && map[p1] !== team) return false;
// map[p1] = team;
// for (const p2 of graph[p1]) {
// if (!(p2 in map)) stack.push([p2, !team]);
// }
// }
// }
// return true;
// };
const makeGraph = (arr) => {
const graph = {};
for (const pair of arr) {
const [p1, p2] = pair;
graph[p1] === undefined && (graph[p1] = []);
graph[p2] === undefined && (graph[p2] = []);
graph[p1].push(p2);
graph[p2].push(p1);
}
return graph;
};
console.log(
tolerantTeams([
["philip", "seb"],
["raj", "nader"],
])
);
// -> true
// // philip : seb
// // seb : philip
// // raj : nader
// // nader: raj
// // t1 => p, r
// // t2 => s, n
console.log(
tolerantTeams([
["philip", "seb"], // !t1.includes(p1) && !t2.includes(p1) && t1.push(p1) && t2.push(p2)
["raj", "nader"], // t2.includes(p1) && t1.push(p2)
["raj", "philip"], // t1.includes(p1) && t2.push(p2)
["seb", "raj"],
])
);
// -> false
// philip : [seb, raj]
// seb : [philip, raj]
// raj : [philip, nader, seb]
// nader: [raj]
// t1 => p,
// t2 => s, r, n
// const tolerantTeams = (rivalries) => {
// const graph = makeGraph(rivalries);
// const visited = new Set();
// const t1 = [];
// const t2 = [];
// // for (const p in graph) {
// // const stack = [p];
// // if (visited.has(p)) continue;
// // visited.add(p);
// // while (stack.length > 0) {
// // const p1 = stack.pop();
// // // !t1.includes(p1) && !t2.includes(p1) && t1.push(p1);
// // // if (!t1.includes(p1) && t2.includes(p1)) continue;
// // for (const nei of p1) {
// // !visited.has(nei) && stack.push(nei);
// // // !t1.includes(nei) && !t2.includes(nei) && t2.push(nei);
// // }
// // }
// // }
// return graph;
// };