First Edge That Breaks Two-Colouring
HardGraphs
Problem
A seating planner places n guests numbered 0 to n - 1 at two tables. Incompatibilities arrive one at a time in edges: each [a, b] means guests a and b must sit at different tables. An entry [a, a] means guest a cannot be seated at all.
Return the 0-based index of the first incompatibility after which no valid split into two tables exists, or -1 if every incompatibility can be honoured.
Example 1
- Input:
- n = 4, edges = [[0, 1], [1, 2], [2, 3], [3, 0], [0, 2]]
- Output:
- 4
The first four form an even cycle (tables {0, 2} and {1, 3}). Edge 4 asks 0 and 2 to separate, which is impossible.
Example 2
- Input:
- n = 3, edges = [[0, 1], [1, 2]]
- Output:
- -1
Example 3
- Input:
- n = 3, edges = [[0, 1], [0, 1], [1, 2], [2, 0]]
- Output:
- 3
A repeated pair is harmless; closing the triangle is not.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ edges.length ≤ 2·10^5
- 0 ≤ a, b < n
Hint
Show the first hint
Rerunning a full bipartite check after every edge is correct but slow. What do you need to remember about each group of connected guests?
Walkthrough
How to approach it
01Clarify before coding
- Is an incompatibility with oneself possible? Yes, [a, a] can never be honoured.
- Do repeated pairs matter? No, they repeat a constraint already satisfied.
- Should later edges be considered after the first failure? No, return the first failing index.
02Brute force
After adding each edge, rerun a BFS two-colouring of the whole graph and stop at the first failure.
Cost: O(E · (n + E)): about 6·10^10 steps at the limits. Binary searching the index brings it to O((n + E) log E), but that does not generalise to true online queries.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.