Check if two-group seating is possible
Overview
This question evaluates understanding of graph theory concepts—particularly bipartiteness and graph traversal—and competency in algorithm design and implementation within the Coding & Algorithms domain, emphasizing practical application of traversal-based reasoning rather than purely conceptual theory.
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.