Funcia
Lv.2bfsbipartitegraph

Split Rivals into Two Teams

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Split n players into two teams so that no rival pair rivals[i] = [a, b] shares a team. Return whether that is possible (a team may be empty).

Examples

nrivalsresult
4[[0, 1], [1, 2], [2, 3]]true
3[[0, 1], [1, 2], [2, 0]]false
5[]true

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(n: int, rivals: int[][]) → bool

Constraints

  • 1≤1 \le n ≤100,000\le 100{,}000, 0≤0 \le rivals.length ≤200,000\le 200{,}000
  • 0≤a,b<n0 \le a, b < n; pairs may repeat and a == b makes it impossible.

Expected complexity

Time
O(N + M)
Space
O(N + M)

Examples

nrivalsExpected
4[[0,1],[1,2],[2,3]]true
3[[0,1],[1,2],[2,0]]false
5[]true

Hint

Hint

Bipartite check: BFS-colour every uncoloured player, giving rivals the opposite colour; a rival with the same colour means false. Trying all 2n2^n splits exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251488 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness409verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.