Standard Bar Graphs · Traversal Problems O(V + E) · O(V)
A hospital roster treats staff as nodes and every conflicting duty pair as an edge. The scheduler wants to split everyone into exactly two shifts so that no conflicting pair lands on the same shift. That split exists precisely when a two-colouring of the conflict graph never paints linked people alike; one odd-length conflict ring ruins the whole roster.
Input: An adjacency list graph where graph[u] lists every node adjacent to u (undirected, no self-loops, possibly disconnected).
Output: Return true if the nodes can be split into two independent sets with every edge crossing between them, otherwise false.
1 <= graph.length <= 1000 <= graph[u].length < graph.lengthNo self-edges or parallel edgesInput: {"graph":[[1,2,3],[0,2],[0,1],[0]]}
Output: false
Nodes 0, 1 and 2 form a triangle — three people in a ring cannot share two shifts.
Input: {"graph":[[1,3],[0,2],[1,3],[0,2]]}
Output: true
The four-cycle colours alternately with no conflict.