405. Two Clique Problem

Given an undirected graph with n vertices (0-indexed) and m edges, determine whether its vertices can be split into exactly two groups such that each group forms a clique (every pair of vertices within the same group is connected by an edge). Print 'Yes' or 'No'.

Input: The first line contains n, the number of vertices. The second line contains m, the number of edges. Each of the next m lines contains two integers, an undirected edge. Output: Print 'Yes' if the vertices can be split into exactly two cliques, otherwise print 'No'.

1 <= n <= 200

This is a beautiful example of REDUCING a seemingly novel problem (two-clique-splitting) to a well-known, already-solved one (bipartite checking) via a clever graph transformation (complementation) - recognizing such reductions is a hallmark of strong algorithmic thinking.

Check whether a graph's vertices can be split into exactly two groups, each forming a clique (every pair within a group connected). Brute force: Try every possible way of splitting n vertices into two groups directly and check if each forms a clique - this is exponential (2^n possible splits), impractical for larger graphs. Optimised: The elegant reduction 'splittable into two cliques' equals 'complement graph is bipartite' transforms an exponential-looking search into a standard, efficient 2-coloring check - and since checking 'complement-adjacency' just means checking 'NOT adjacent in the original', the complement never needs to be explicitly constructed, saving significant memory for dense graphs.

Build the complement graph, where an edge exists between two vertices exactly when no edge existed between them in the original graph, and check whether this complement graph is bipartite using a standard BFS/DFS two-coloring. This works because splitting the original graph into two cliques is possible exactly when the complement graph can be split into two independent sets, which is precisely the definition of bipartiteness; the two color classes found are the two cliques. This turns an exponential search into a polynomial-time check by recognizing the problem as a disguised bipartiteness test. Time: O(n^2) Space: O(n^2)

Assign vertices to one of the two groups one at a time in some fixed order, and immediately reject an assignment the moment placing a vertex into a group would create a non-adjacent pair within that group, backtracking to try the other group instead. This explores far fewer than all 2^n partitions in practice because invalid branches are cut off as soon as a conflict appears, rather than being fully built and checked afterward as in the brute-force approach, though the worst case is still exponential. Time: O(2^n) worst case, far fewer in practice Space: O(n)

Try every one of the 2^n ways to split the n vertices into two labeled groups, and for each split check whether both groups are cliques by testing every pair of vertices within each group for an edge. If any split passes, print 'Yes'. This directly checks the problem's definition for every possible partition, so it's unquestionably correct, but the exponential number of partitions makes it usable only for tiny graphs. Time: O(2^n * n^2) Space: O(n^2)

1. Recognize the key insight: a graph splits into two cliques EXACTLY when its COMPLEMENT graph (edges flipped: connected in complement iff NOT connected in original) is BIPARTITE. 2. You don't need to build the complement graph explicitly - when checking neighbors during a BFS/DFS 2-coloring pass, just treat 'NO edge between u and v in the original' as 'u and v ARE complement-adjacent'. 3. Run the standard bipartite check (2-color via BFS/DFS, fail if a complement-edge ever connects two same-colored vertices) over every component of the COMPLEMENT graph.

Time: O(n²) - checking complement-adjacency (a NOT-edge check) between every pair of vertices during the 2-coloring pass. Space: O(n), for the color-tracking array (the original graph's own adjacency structure is reused directly, no explicit complement graph built).

Test a graph with no edges at all (m = 0, complement is complete, likely splittable), a graph that's already a single clique, and n at the upper bound of 200.

Be ready to explain the clique-to-independent-set-to-bipartite reduction chain clearly: a clique in the original becomes an INDEPENDENT SET in the complement, and 'splittable into 2 independent sets' is EXACTLY the definition of bipartite - each step of this reduction is worth being able to state explicitly.