mediumGraphsPure DSA~25 min
Can the Conflict Graph Be Split Into Two Cohorts
Each edge marks two accounts that must be kept in different experiment cohorts. Decide whether everyone can be assigned to exactly one of two cohorts so that no conflicting pair shares a cohort.
Problem
Given an undirected graph with n nodes (0..n-1) as an adjacency list graph, return true if the graph is bipartite — its nodes can be 2-colored so that every edge connects nodes of different colors — and false otherwise.
Input
An adjacency list graph where graph[u] lists u's neighbors.
Output
A boolean: whether the graph is bipartite.
Constraints
- 1 <= n <= 100
- 0 <= graph[u].length < n
- The graph may be disconnected and has no self-loops or parallel edges.
Examples
Example 1
Input
graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output
false
Nodes 1 and 2 are adjacent yet both must differ from 0, forcing a conflict.
Example 2
Input
graph = [[1,3],[0,2],[1,3],[0,2]]
Output
true
Color {0,2} one cohort and {1,3} the other.