Check if two-group seating is possible

Given an undirected graph represented as an adjacency list where adj[i] lists the indices of guests who know guest i, determine whether all guests can be seated using at most two groups such that no two guests in the same group know each other. Return true if such a seating is possible, otherwise false. Describe and implement an algorithm that handles disconnected components, and analyze time and space complexity. State assumptions about bidirectionality of edges, presence of self-loops or duplicate entries, and outline edge cases and tests.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Check if two-group seating is possible

You are given an undirected graph as an adjacency list adj, where adj[i] lists the indices of guests who know guest i. You must seat every guest into at most two groups so that no two guests in the same group know each other.

Return true if such a two-group seating is possible, otherwise false.

This is equivalent to deciding whether the friendship graph is bipartite. Your solution must handle disconnected components (run the check from every unvisited node).

Assumptions (state these before coding):

• Edges are bidirectional: if j appears in adj[i], the pair (i, j) is an undirected acquaintance edge. (The reference treats edges that appear from either endpoint; for a well-formed input each edge is listed on both sides.)
• A self-loop (i in adj[i]) means a guest "knows" themselves and they cannot be placed in any group consistently, so the answer is false.
• Duplicate entries in an adjacency list are harmless and treated the same as a single edge.
• Guests are indexed 0 .. n-1 where n = len(adj).

Example 1: adj = [[1], [0]] -> true (two guests who know each other go in different groups).

Example 2: adj = [[1,2],[0,2],[0,1]] -> false (a triangle / odd cycle cannot be 2-colored).

Example 3: adj = [] -> true (no guests, vacuously seatable).

Constraints

• 0 <= n <= 10^5 where n = len(adj)
• 0 <= adj[i][k] < n (indices are valid guests)
• Total number of adjacency entries (edges counted from both sides) up to ~2*10^5
• Input may contain disconnected components, duplicate entries, or self-loops
• Return a boolean

Hints

1. Two groups + 'same group must not know each other' is exactly a graph 2-coloring problem. The answer is 'is the graph bipartite?'
2. BFS or DFS from each unvisited node, assigning the opposite color to every neighbor. A conflict (a neighbor already has the same color) means it is impossible.
3. Iterate the outer loop over ALL nodes so disconnected components are each colored. A self-loop is an instant failure since the node would need a different color from itself.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Given an undirected graph represented as an adjacency list where adj[i] lists the indices of guests who know guest i, determine whether all guests can be seated using at most two groups such that no two guests in the same group know each other. Return true if such a seating is possible, otherwise false. Describe and implement an algorithm that handles disconnected components, and analyze time and space complexity. State assumptions about bidirectionality of edges, presence of self-loops or duplicate entries, and outline edge cases and tests.

Recommended Approach

Model the states explicitly and use BFS for unweighted shortest paths, Dijkstra for weighted non-negative paths, or topological DP for DAGs. Track visited states at the right granularity so cycles do not cause repeated work.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

BFS is O(V + E) time and O(V) space for a standard graph. Expanded-state problems multiply those bounds by the number of state dimensions.

Edge Cases and Tests

Disconnected graph, source equals target, cycles, duplicate edges, unreachable target, and whether the answer counts nodes, edges, moves, or transfers.