Two Buses for the Trip
A teacher is taking the class to the science museum in two buses. Over the year she has learned which pairs of kids cannot sit near each other without trouble, and she wants every such pair on different buses. Buses are big, so there is no limit on how many kids ride in each.
Some lists are impossible. If Ana clashes with Ben, Ben with Cara, and Cara with Ana, then whichever bus Ana takes, one of the other two has to join her. The teacher wants to know before she makes the seating plan.
Your task
Write canSplit(n, clashes). The kids are numbered 0 to n - 1. Each [a, b] in clashes means kids a and b must ride different buses. Return true if every kid can be put on one of the two buses so that no clashing pair shares a bus, otherwise false.
A kid with no clashes can ride either bus. The same pair may be listed more than once.
canSplit(n: int, clashes: int[][]) → bool
Examples
n = 4 clashes = [[0, 1], [1, 2], [2, 3], [3, 0]]
true
The clashes form a loop of four. Put 0 and 2 on bus A, and 1 and 3 on bus B. Every clash crosses between the buses.
n = 3 clashes = [[0, 1], [1, 2], [2, 0]]
false
The triangle from the story. 0 on bus A forces 1 onto B, which forces 2 onto A, but 2 clashes with 0. No assignment works.
Constraints
- 1 ≤ n ≤ 2,000
- 0 ≤ clashes.length ≤ 5,000
- 0 ≤ a, b < n and a ≠ b
Start with brute force
Try every way to assign the kids: each kid gets bus A or B, so there are 2n assignments, and check each against the clash list.
With 40 kids that is already over a trillion assignments, and n can be 2,000. Almost all of that work is wasted, because placing one kid forces everyone connected to them.
Hints
0 of 4 shown- Hint 1
Put kid 0 on bus A in the first example. Do you now have any choice about kid 1? About kid 3? What about kid 2?
- Hint 2
Once one kid in a connected group is placed, every other kid in that group is forced: each clash pushes the neighbor onto the opposite bus. The only question is whether those forced choices ever contradict each other.
- Hint 3
Spread the bus assignments outward with a search, like paint flowing along the clash lines. A contradiction is a clash where both kids ended up on the same bus. What about kids that the search from kid 0 never reaches?
- Hint 4
Keep
bus[i]as unset, 0 or 1. Loop over every kid; if one is still unset, give it bus 0 and run a breadth-first search from it. For each neighbor: if unset, give it the opposite bus and queue it; if it already has the same bus as the current kid, return false. If every search finishes cleanly, return true.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Think of kids as nodes and clashes as edges. In one connected group, placing a single kid decides everyone else: a neighbor goes on the opposite bus, their neighbors on the opposite of that, and so on. So you never need to guess. Spread the assignment with a search and watch for a clash that lands both kids on the same bus.
Trace the triangle, n = 3, clashes 0-1, 1-2, 2-0:
- Kid 0 is unplaced. Put it on bus 0 and queue it.
- Take 0. Neighbor 1 is unplaced: bus 1. Neighbor 2 is unplaced: bus 1. Queue both.
- Take 1. Neighbor 0 is on bus 0, different, fine. Neighbor 2 is on bus 1, the same as kid 1. Return false.
On the loop of four, the same process gives 0 → bus 0, 1 and 3 → bus 1, 2 → bus 0, and every clash checks out, so it returns true.
The outer loop matters. Kids with no link to kid 0 form their own groups, and a contradiction can hide in any of them. Starting a fresh search from every unplaced kid covers them all.
function canSplit(n, clashes) {
const adj = Array.from({ length: n }, () => []);
for (const [a, b] of clashes) {
adj[a].push(b);
adj[b].push(a);
}
const bus = new Array(n).fill(-1); // -1 = not placed yet
for (let start = 0; start < n; start++) {
if (bus[start] !== -1) continue;
bus[start] = 0; // a new group: either bus is fine
const queue = [start];
for (let head = 0; head < queue.length; head++) {
const kid = queue[head];
for (const other of adj[kid]) {
if (bus[other] === -1) {
bus[other] = 1 - bus[kid]; // forced onto the other bus
queue.push(other);
} else if (bus[other] === bus[kid]) {
return false; // a clash on the same bus
}
}
}
}
return true;
}from collections import deque
def can_split(n, clashes):
adj = [[] for _ in range(n)]
for a, b in clashes:
adj[a].append(b)
adj[b].append(a)
bus = [-1] * n # -1 = not placed yet
for start in range(n):
if bus[start] != -1:
continue
bus[start] = 0 # a new group: either bus is fine
queue = deque([start])
while queue:
kid = queue.popleft()
for other in adj[kid]:
if bus[other] == -1:
bus[other] = 1 - bus[kid] # forced onto the other bus
queue.append(other)
elif bus[other] == bus[kid]:
return False # a clash on the same bus
return TrueRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.