678. Two-Team Split
A group of n people, numbered 0 to n-1, is described by adjacency lists: graph[u] holds the people who are direct acquaintances of person u. Acquaintance is mutual, so v appears in graph[u] exactly when u appears in graph[v]; nobody lists themself and no list repeats a person.
The organiser wants to place everyone into one of two teams so that no two acquaintances share a team. Return true if such a split exists, otherwise false. The group may consist of several unconnected clusters, and some lists may be empty. Use iterative traversal. The expected cost is O(n + e) time and O(n) space, where e is the number of acquaintance pairs.
Example 1
- Input:
- graph = [[1,4],[0,2],[1,3],[2,4],[3,0]]
- Output:
- false
- Explanation:
The five people form a ring of odd length, so alternating teams must clash somewhere; the answer is false.
Example 2
- Input:
- graph = [[1],[0,2],[1],[4],[3],[]]
- Output:
- true
- Explanation:
Put 0 and 2 on one team and 1 on the other, 3 and 4 on opposite teams, and 5 anywhere; every acquaintance pair is split.
Example 3
- Input:
- graph = [[1,5],[0,2],[1,3],[2,4],[3,5],[4,0]]
- Output:
- true
- Explanation:
A ring of six alternates cleanly between the two teams.
Constraints
1 ≤ n ≤ 100000
0 ≤ total length of all lists ≤ 400000
graph is symmetric, has no self-loops and no repeated neighbours
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n + e)
- Space
- O(n)