On this page

2-SAT, Graph Coloring & Other Classic Graph Problems

Why this exists

Most of this module has been about problems with fast, exact algorithms: shortest paths, spanning trees, flows, matchings. This lesson sits on the border. It covers a group of famous problems where a tiny change in the statement moves you from "linear time" to "nobody knows how to do better than exponential". Knowing which side of the border a problem lives on is the single most useful skill here, because it tells you whether to look for a clever polynomial algorithm or to reach for exponential search on small inputs, a heuristic, or an approximation.

2-SAT is the cleanest example. You are given boolean variables and a list of constraints, each saying "at least one of these two literals is true". Deciding whether all constraints can hold at once takes time, using nothing more than the strongly connected components from the connectivity lesson. Allow three literals per constraint and you have 3-SAT, the original NP-complete problem (Cook 1971, Karp 1972). The 2-literal case was shown to be polynomial by Krom (1967), and the linear-time algorithm via the implication graph is due to Aspvall, Plass and Tarjan (1979). It turns up whenever every decision is binary and every rule involves two decisions: which side of a ring a road goes on, whether a map label goes above or below its point, which of two time slots a meeting gets.

Graph colouring is the other headliner. Assign each vertex a colour so that adjacent vertices differ, using as few colours as possible. Two colours is the bipartite test you already know from BFS and runs in linear time; three colours is NP-complete. Yet colouring is everywhere: compilers colour an interference graph to assign variables to CPU registers (Chaitin, 1981), exam schedulers colour a conflict graph to assign time slots, radio planners colour an interference graph to assign frequencies, and the famous four-colour theorem says every planar map needs at most four. Around colouring sit its relatives: maximum clique, maximum independent set, minimum vertex cover and minimum dominating set, all NP-hard in general, all solvable for small or structured inputs with techniques this lesson teaches.

The NP-completeness theory itself (reductions, the P versus NP question, approximation hardness) belongs to the Complexity Theory lesson in Module 9 (Advanced Topics). Here we take the results as given and focus on what an engineer actually does: solve 2-SAT exactly, colour greedily with known guarantees, solve exactly when is small, and approximate when it is not.

Pattern triggers

If the problem says or has…Think of…
Every item has exactly two options (on/off, left/right, inside/outside) and rules relate pairs of items2-SAT on the implication graph
"at least one of A, B", "not both A and B", "A implies B", "A and B differ / are equal"2-SAT clauses (each rule becomes one or two clauses)
"each of these people wants one of two things satisfied"2-SAT, one clause per person (CSES Giant Pizza)
Rules that mention three items at once ("at least one of A, B, C")Not 2-SAT; 3-SAT is NP-complete. Look for structure or small
Only XOR / equality constraints between pairsParity union-find or 2-SAT; both linear
"split into two groups so that no conflicting pair is in the same group"Bipartite check (2-colouring)
"minimum number of groups / rooms / time slots so that conflicting items are separated"Graph colouring; if the conflicts are interval overlaps, greedy by start time is optimal
Every vertex has degree at most and you need any valid colouring with coloursGreedy colouring, any order
– and you need the exact chromatic numberSubset DP, , or inclusion–exclusion,
"largest group of mutually compatible / mutually friendly items", –Maximum clique or independent set: Bron–Kerbosch with pivoting, or meet in the middle
"fewest vertices touching every edge", general graphMinimum vertex cover; NP-hard, 2-approximation via maximal matching
The same, but the graph is bipartiteKönig's theorem: min vertex cover = max matching (matching lesson)
The same, but the graph is a treeTree DP, linear time (and similar for dominating set)
Planar map, regions sharing a border must differFour colours always suffice; deciding three is NP-complete

The meta-trigger: binary choices plus pairwise rules is easy; anything that forces you to choose among three or more options per item, or that couples three items in one rule, is probably hard. When it is hard, look at : up to about 20 means subset DP, up to about 40 means meet in the middle or branch and bound, and beyond that means heuristics or exploiting special structure (bipartite, tree, interval, planar, bounded degree).

Intuition & first principles

From clauses to implications

A literal is a variable or its negation: or . A 2-clause is a disjunction of two literals, . A 2-CNF formula is a conjunction of 2-clauses. The problem is to find an assignment that makes every clause true, or report that none exists.

The key observation: is logically the same as two implications,

If is false, is forced to be true, and vice versa. So build a directed graph with one vertex per literal ( vertices for variables) and two edges per clause: and . This is the implication graph. A path means "if is true then must be true", because implications chain.

Now the whole problem becomes a question about reachability. If there is a path , then setting true forces false, so must be false. If there is also a path , then must be true as well, which is impossible. Paths in both directions between two vertices mean they are in the same strongly connected component. So:

A 2-CNF formula is unsatisfiable if and only if some variable has and in the same SCC.

The "only if" direction (if no such variable exists, an assignment exists) is the clever half, and its proof also tells you how to build the assignment: process the condensation DAG and give each literal the value "true" when its component comes later in topological order than its negation's component. Intuitively, a literal late in the order implies little (it is near the sinks), so making it true forces little; a literal early in the order would drag a long chain of consequences along with it.

Why three literals break everything

With , falsifying no longer forces anything on its own; it forces " or ", a disjunction, and disjunctions do not chain into a graph. That is exactly the step where 3-SAT becomes NP-complete. The same divide shows up elsewhere: 2-colouring is BFS, 3-colouring is NP-complete; bipartite matching is polynomial, 3-dimensional matching is NP-complete. "Two" is special because a single choice determines the other.

Colouring: why greedy works sometimes and fails badly other times

Greedy colouring: walk the vertices in some order, and give each the smallest colour not used by an already-coloured neighbour. A vertex with neighbours sees at most forbidden colours, so some colour in is free. Hence greedy never uses more than colours, where is the maximum degree. That bound is tight for complete graphs ( has and needs colours) and odd cycles (, need 3). Brooks' theorem (1941) says those are the only connected graphs that need ; every other connected graph can be coloured with .

The weakness of greedy is the order. Every graph has some order in which greedy is optimal (order the vertices by colour class of an optimal colouring), but a bad order can be terrible. The classic example is the crown graph: two rows and , with adjacent to whenever . It is bipartite, so two colours suffice, yet visiting it in the order forces greedy to use colours: and are not adjacent and both see colours from earlier pairs, so both get colour . The implementation below asserts that this happens for .

Heuristic orders fix much of this in practice. Welsh–Powell (1967) colours vertices in decreasing order of degree, so the hardest-constrained vertices get small colours first. DSATUR (Brélaz, 1979) is dynamic: at each step, colour the uncoloured vertex with the highest saturation degree (number of distinct colours already among its neighbours), breaking ties by degree. DSATUR is exact on bipartite graphs, cycles and wheels, and on random graphs it is usually within a colour or two of optimal. None of these heuristics has a good worst-case ratio; no polynomial algorithm can approximate the chromatic number within unless P = NP (Zuckerman, 2007).

Exact colouring by subsets

A colouring with colours is a partition of the vertices into independent sets (sets with no internal edges). That reframing gives two exact algorithms for small :

  • Subset DP. Let be the minimum number of colours needed for the induced subgraph on vertex set . Then and over non-empty independent subsets . Enumerating all submasks of all masks costs .
  • Inclusion–exclusion. Let be the number of independent sets (including the empty set) inside . The number of ordered -tuples of independent sets whose union is all of is

and is -colourable exactly when . Computing all takes with the recurrence , and testing costs per , so total. This is the Björklund–Husfeldt–Koivisto algorithm (2009).

For : against . The difference between "a minute" and "a few hundredths of a second".

Mechanics

Building the implication graph

Take four variables and five clauses:

Each clause adds and :

ClauseEdge 1 ()Edge 2 ()
flowchart LR
    x1["x1"] --> x3["x3"]
    x3 --> x4["x4"]
    x4 --> nx1["¬x1"]
    nx1 --> x2["x2"]
    x2 --> x3
    x1 --> nx4["¬x4"]
    nx4 --> nx3["¬x3"]
    nx3 --> nx1
    nx3 --> nx2["¬x2"]
    nx2 --> x1

Notice the skew symmetry: the graph is its own mirror image under "negate everything and reverse every edge". is paired with , and so on. That symmetry is what the correctness proof relies on.

Read the chain : if were true, it would force itself false. So is false, which then forces (via ), which forces and .

The algorithm

flowchart TD
    A["Read n variables and m clauses"] --> B["Build implication graph<br/>2n vertices, 2m edges"]
    B --> C["Compute SCCs<br/>Kosaraju or Tarjan"]
    C --> D{"x and ¬x in the same SCC<br/>for some x?"}
    D -->|"yes"| U["UNSATISFIABLE"]
    D -->|"no"| E["x = true iff comp of x comes<br/>after comp of ¬x in topological order"]
    E --> F["Output assignment"]

Kosaraju's algorithm numbers components in topological order of the condensation (component 0 is a source). So with Kosaraju, is true iff . Tarjan's algorithm emits components in reverse topological order (the first completed component is a sink), so with Tarjan the test flips: is true iff . Getting this backwards is the most common 2-SAT bug, and it produces assignments that look plausible and fail on some clauses.

Trace: Kosaraju on the example

Computed by a throwaway script running exactly the implementation below. Literal indices: , , and adjacency lists in clause order. Pass 1 runs DFS on the implication graph, starting from vertex 0 (), and records finishing order:

StepEventDFS stack (bottom → top)Finish order so far
1visit —
2visit —
3visit —
4visit —
5visit ; its only edge goes to (seen)—
6finish , , ,
7visit (second edge of )same
8visit same
9 seen; visit ; its edge to is seensame
10finish , , , —

Pass 2 walks the reversed graph in reverse finishing order. Starting from (finished last), it reaches : component 0. The next unassigned vertex in reverse finishing order is , which reaches : component 1. The condensation has a single edge, component 0 → component 1 (from ).

VariablecompcompSame SCC?Value ()
01nofalse
10notrue
10notrue
10notrue

Assignment . Check every clause: true; true; true; true; true. Brute force over all 16 assignments confirms this is the only satisfying one, as the forced chain predicted.

For an unsatisfiable formula, take all four clauses on two variables: . All four literals end up in one SCC, and the solver reports failure.

Modelling constraints as clauses

Most of the skill in 2-SAT is in the encoding. Every constraint between two boolean variables can be written with at most four clauses, because a constraint on two variables forbids some of the four combinations, and each forbidden combination is ruled out by exactly the clause .

ConstraintClausesNotes
is true (force)Adds edge
not both and (NAND)
at least one of
(exactly one, XOR)
(equal)
at most one of for all clauses; a prefix ("sequential counter") encoding with helper variables uses (Sinz, 2005)
exactly one of , not expressible"at least one of " is a -clause

The last row is the boundary of the technique. If a problem needs "pick one of three colours for each vertex", it is 3-colouring and no 2-SAT encoding exists (unless P = NP). The usual trick when each item has three or more options is to look for a structural reason why only two remain live, for example after fixing some decision by brute force.

Example: the ring road. Cities sit on a circle; some new roads connect pairs of cities and each must be built either inside or outside the circle; two roads whose endpoints interleave around the circle would cross if built on the same side. Variable = "road goes inside". For each crossing pair add . That is Codeforces 27D, and since all constraints are XOR it is also just a bipartite check on the "crossing" graph: 2-SAT generalizes 2-colouring.

Example: Giant Pizza (CSES 1684). Each person states two wishes, each of the form "include topping " or "exclude topping ", and is happy if at least one wish is granted. One variable per topping, one clause per person. A direct application, and a good first test of your solver at clauses.

Greedy colouring and DSATUR, by hand

Use this six-vertex graph with edges 0–1, 0–2, 0–3, 1–2, 1–4, 2–3, 2–4, 3–5, 4–5. It contains triangles (0, 1, 2), so at least three colours are needed.

flowchart LR
    v0(("0 : c1")) --- v1(("1 : c2"))
    v0 --- v2(("2 : c0"))
    v0 --- v3(("3 : c2"))
    v1 --- v2
    v1 --- v4(("4 : c1"))
    v2 --- v3
    v2 --- v4
    v3 --- v5(("5 : c0"))
    v4 --- v5

The labels show the DSATUR result. Its trace (saturation is measured before colouring; ties broken by uncoloured degree, then by lowest index):

StepChosen vertexSaturationUncoloured neighboursNeighbour coloursColour given
1204—0
2012{0}1
3121{0, 1}2
4321{0, 1}2
5421{0, 2}1
6520{1, 2}0

Plain greedy in the natural order 0, 1, …, 5 gives colours and Welsh–Powell (degree order 2, 0, 1, 3, 4, 5) gives the same colouring as DSATUR. All use three colours, which is optimal: the exact algorithms agree. On the crown graph with , natural-order greedy uses 4 colours while DSATUR uses 2.

The ladder: brute force → better → optimal

There are two ladders here, because 2-SAT has a polynomial top rung and colouring does not.

2-SAT

Rung 1: try every assignment. assignments times clauses: . Fine for , hopeless at .

Rung 2: unit propagation with backtracking. Pick an unassigned variable, set it, propagate forced values; if a contradiction appears, flip it. For 2-SAT specifically this never needs deep backtracking: if setting true and propagating gives a contradiction, then must be false, and propagating that is final (Even, Itai and Shamir, 1976). This gives : each variable is tried at most twice, each propagation is .

Rung 3: implication graph and SCCs. One SCC computation, . Each improvement comes from the same fact used more cleverly: implications chain, and chains are graph paths. Rung 2 follows the chains one at a time; rung 3 computes all of them at once with a single pair of DFS passes.

Chromatic number

Rung 1: try every colouring. colourings for each . At , : ; at , : .

Rung 2: backtracking with pruning. Colour vertices in DSATUR order, try colours , backtrack on conflict. Exponential in the worst case but far faster than rung 1 in practice; DSATUR-based branch and bound (Brélaz; later San Segundo and others) solves random graphs with around 70–100 vertices.

Rung 3: subset DP, . Memoize over vertex subsets instead of over partial colourings. All colourings of the same subset with the same count collapse into one state.

Rung 4: inclusion–exclusion, . Count covers instead of searching for them. The best known exact bound for general graphs.

ProblemApproachTimeSpacePractical limit
2-SATBrute force
2-SATPropagate and fix (Even–Itai–Shamir)
2-SATImplication graph + SCC clauses
ColouringAll colourings
ColouringDSATUR branch and boundexponential– random
ColouringSubset DP–
ColouringInclusion–exclusion–
ColouringGreedy / Welsh–Powell / DSATUR to any , no optimality guarantee

Correctness

2-SAT: the SCC criterion

Lemma (skew symmetry). The implication graph has an edge iff it has the edge . Consequently there is a path iff there is a path , and are in the same SCC iff are.

Proof. Edges are added in pairs: clause adds and , and the second is the "negate and reverse" image of the first. Reversing every edge of a path and negating every vertex gives a path in the other direction.

Lemma (soundness of edges). Under any satisfying assignment, if is true and , then is true.

Proof. Each edge comes from the clause ; if is true then is false, and the clause forces . Induct along the path.

Theorem. The formula is satisfiable iff no variable has and in the same SCC.

Proof of "only if". Suppose and share an SCC, so and . In any assignment, either is true, and the first path forces true, or is true, and the second path forces true. Both are contradictions, so no satisfying assignment exists.

Proof of "if", constructively. Number the SCCs in a topological order of the condensation, so every edge satisfies (equal inside a component, strictly increasing across). Kosaraju produces exactly such a numbering. Set true iff ; this is well defined because the two are never equal. Equivalently, a literal is true iff , for both and .

Suppose some clause is false: false and false, so and . The clause contributed edges and , so and . Chaining:

a contradiction. So every clause is satisfied.

The proof uses only "edges never go backwards in the numbering", which is why any topological numbering works and why Tarjan's reverse numbering needs the flipped comparison.

Greedy colouring: the bound and interval optimality

Bound. When vertex is coloured, at most of its neighbours are already coloured, so at most colours are excluded and the smallest free colour is at most . Colours are : at most . A sharper version: if every vertex has at most neighbours earlier in the order, greedy uses at most colours. Choosing the order "repeatedly remove a minimum-degree vertex, then colour in reverse removal order" achieves = the degeneracy of the graph, which can be far smaller than (a star has but degeneracy 1). Planar graphs have degeneracy at most 5, because Euler's formula gives and so some vertex has degree at most 5: six colours, by greedy, in linear time.

Interval graphs. Vertices are intervals; edges join overlapping intervals. Colour in increasing order of start time with the smallest free colour. When interval receives colour , colours are each held by some earlier interval overlapping . Every such interval starts no later than and overlaps , so it contains the start point of . Together with that is intervals sharing a common point: a clique of size . So the number of colours greedy uses equals the size of some clique, which is a lower bound on any colouring. Greedy is optimal, and the answer is the maximum number of intervals covering a single point. That is the "minimum meeting rooms" problem from the intervals lesson, solved in with a sort and a heap.

Inclusion–exclusion for colouring

Fix . Count ordered -tuples of independent sets (possibly empty, possibly overlapping) whose union is . For a set , the number of -tuples with every is . By inclusion–exclusion over the set of uncovered vertices, the number of tuples covering all of is . A covering tuple exists iff a proper -colouring exists: given a cover, colour each vertex with the index of the first set containing it (subsets of independent sets are independent); given a colouring, its colour classes form a cover.

Bron–Kerbosch with pivoting

The recursion keeps three disjoint sets: , the clique being built; , the vertices adjacent to all of that may still be added; and , the vertices adjacent to all of that were already explored in a sibling branch. Invariant: is exactly the set of common neighbours of . is a maximal clique iff and are both empty (nothing can extend it). Without , the same maximal clique would be reported once per order of discovery.

Pivoting (Tomita, Tanaka and Takahashi, 2006): pick any . Every maximal clique containing contains either or some non-neighbour of ; otherwise could be added to it. So it suffices to branch only on . Choosing to maximize minimizes the branching, and the resulting worst case is , which matches the Moon–Moser bound: a graph on vertices has at most maximal cliques, attained by the complete multipartite graph with parts of size 3. The implementation asserts the count of 27 maximal cliques on .

The 2-approximation for vertex cover

Take any maximal matching (greedily add edges with both endpoints unmatched) and output all endpoints. It is a cover: an uncovered edge would have two unmatched endpoints and could be added to , contradicting maximality. It is at most twice optimal: the edges of share no endpoints, so any cover needs a distinct vertex for each, giving . Hence the output has size .

Complexity

  • 2-SAT: vertices and edges; two DFS passes; time and memory. The constants are small, but the graph has twice as many vertices and edges as the formula has variables and clauses, so at clauses expect around adjacency entries plus the reversed copy. A recursive DFS overflows the stack in Python and often in Java at that size; the implementations below are iterative.
  • Greedy colouring: with a per-vertex "used colours" marker array; sorting for Welsh–Powell adds . DSATUR: with the simple scan used below, with a priority queue keyed by (saturation, degree).
  • Chromatic number, subset DP: time, memory. Inclusion–exclusion: time, memory. At the table has entries: 8 MB as 64-bit integers. The values overflow any fixed-width integer, so implementations reduce modulo a large prime. That makes the test "" one-sided: a false "zero" is possible in principle if divides , and it is vanishingly unlikely for a large prime, but it is not a proof. The Python version below uses exact big integers.
  • Bron–Kerbosch with pivoting: worst case; with bitsets each step is a few word operations, so – sparse graphs are routine. Meet in the middle for maximum independent set: or with a lowest-bit DP: about operations per half at .
  • Vertex cover 2-approximation: .

Implementation

2-SAT solver with clause helpers

Iterative Kosaraju, so it handles clauses without recursion limits. The tests use the worked example, the unsatisfiable formula, the helper encodings, and 300 random formulas cross-checked against brute force (the random generator is a fixed xorshift so all four languages run the same formulas).

class TwoSat:
    """2-SAT over variables 0..n-1. Literal 2*v means x_v, 2*v + 1 means NOT x_v."""

    def __init__(self, n: int) -> None:
        self.n = n
        self.adj: list[list[int]] = [[] for _ in range(2 * n)]

    @staticmethod
    def _lit(v: int, value: bool) -> int:
        return 2 * v if value else 2 * v + 1

    def add_clause(self, a: int, va: bool, b: int, vb: bool) -> None:
        """Require (x_a == va) OR (x_b == vb)."""
        la, lb = self._lit(a, va), self._lit(b, vb)
        self.adj[la ^ 1].append(lb)  # if la is false, lb must be true
        self.adj[lb ^ 1].append(la)  # if lb is false, la must be true

    def force(self, a: int, va: bool) -> None:
        self.add_clause(a, va, a, va)

    def implies(self, a: int, va: bool, b: int, vb: bool) -> None:
        self.add_clause(a, not va, b, vb)

    def xor(self, a: int, b: int) -> None:
        self.add_clause(a, True, b, True)
        self.add_clause(a, False, b, False)

    def equal(self, a: int, b: int) -> None:
        self.add_clause(a, True, b, False)
        self.add_clause(a, False, b, True)

    def at_most_one(self, vs: list[int]) -> None:
        for i in range(len(vs)):
            for j in range(i + 1, len(vs)):
                self.add_clause(vs[i], False, vs[j], False)

    def solve(self) -> list[bool] | None:
        size = 2 * self.n
        adj = self.adj
        # Pass 1: iterative DFS, record vertices in finishing order.
        order: list[int] = []
        seen = [False] * size
        for s in range(size):
            if seen[s]:
                continue
            seen[s] = True
            stack = [(s, 0)]
            while stack:
                u, i = stack[-1]
                if i < len(adj[u]):
                    stack[-1] = (u, i + 1)
                    w = adj[u][i]
                    if not seen[w]:
                        seen[w] = True
                        stack.append((w, 0))
                else:
                    stack.pop()
                    order.append(u)
        # Pass 2: reversed graph, reverse finishing order. Ids come out in topological order.
        radj: list[list[int]] = [[] for _ in range(size)]
        for u in range(size):
            for w in adj[u]:
                radj[w].append(u)
        comp = [-1] * size
        c = 0
        for s in reversed(order):
            if comp[s] != -1:
                continue
            comp[s] = c
            stack2 = [s]
            while stack2:
                u = stack2.pop()
                for w in radj[u]:
                    if comp[w] == -1:
                        comp[w] = c
                        stack2.append(w)
            c += 1
        result = []
        for v in range(self.n):
            if comp[2 * v] == comp[2 * v + 1]:
                return None
            result.append(comp[2 * v] > comp[2 * v + 1])  # later in topo order => true
        return result


def satisfies(assign: list[bool], clauses: list[tuple[int, bool, int, bool]]) -> bool:
    return all(assign[a] == va or assign[b] == vb for a, va, b, vb in clauses)


def build(n: int, clauses: list[tuple[int, bool, int, bool]]) -> TwoSat:
    ts = TwoSat(n)
    for a, va, b, vb in clauses:
        ts.add_clause(a, va, b, vb)
    return ts


class XorShift:
    def __init__(self, seed: int) -> None:
        self.x = seed

    def next(self, k: int) -> int:
        x = self.x
        x ^= (x << 13) & 0xFFFFFFFF
        x ^= x >> 17
        x ^= (x << 5) & 0xFFFFFFFF
        self.x = x
        return x % k


if __name__ == "__main__":
    # Worked example: (x1|x2)(~x1|x3)(~x2|x3)(~x3|x4)(~x4|~x1), 0-indexed.
    ex = [(0, True, 1, True), (0, False, 2, True), (1, False, 2, True),
          (2, False, 3, True), (3, False, 0, False)]
    assert build(4, ex).solve() == [False, True, True, True]

    unsat = [(0, True, 1, True), (0, True, 1, False), (0, False, 1, True), (0, False, 1, False)]
    assert build(2, unsat).solve() is None

    ts = TwoSat(3)
    ts.xor(0, 1)
    ts.equal(1, 2)
    ts.force(0, True)
    assert ts.solve() == [True, False, False]

    ts = TwoSat(3)
    ts.at_most_one([0, 1, 2])
    ts.force(1, True)
    ts.implies(1, True, 0, False)
    assert ts.solve() == [False, True, False]

    rng = XorShift(2463534242)
    for _ in range(300):
        n = 1 + rng.next(5)
        m = 1 + rng.next(8)
        cl = [(rng.next(n), rng.next(2) == 1, rng.next(n), rng.next(2) == 1) for _ in range(m)]
        brute = any(satisfies([(mask >> v) & 1 == 1 for v in range(n)], cl) for mask in range(1 << n))
        got = build(n, cl).solve()
        assert (got is not None) == brute
        if got is not None:
            assert satisfies(got, cl)
    print("2-SAT: all tests passed")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class TwoSatDemo {
    static final class TwoSat {
        final int n;
        final List<List<Integer>> adj = new ArrayList<>();

        TwoSat(int n) {
            this.n = n;
            for (int i = 0; i < 2 * n; i++) adj.add(new ArrayList<>());
        }

        static int lit(int v, boolean value) { return value ? 2 * v : 2 * v + 1; }

        /** Require (x_a == va) OR (x_b == vb). */
        void addClause(int a, boolean va, int b, boolean vb) {
            int la = lit(a, va), lb = lit(b, vb);
            adj.get(la ^ 1).add(lb);
            adj.get(lb ^ 1).add(la);
        }

        void force(int a, boolean va) { addClause(a, va, a, va); }
        void implies(int a, boolean va, int b, boolean vb) { addClause(a, !va, b, vb); }
        void xor(int a, int b) { addClause(a, true, b, true); addClause(a, false, b, false); }
        void equal(int a, int b) { addClause(a, true, b, false); addClause(a, false, b, true); }
        void atMostOne(int[] vs) {
            for (int i = 0; i < vs.length; i++)
                for (int j = i + 1; j < vs.length; j++) addClause(vs[i], false, vs[j], false);
        }

        boolean[] solve() {
            int size = 2 * n;
            int[] order = new int[size];
            int ordLen = 0;
            boolean[] seen = new boolean[size];
            int[] stackV = new int[size], stackI = new int[size];
            for (int s = 0; s < size; s++) {
                if (seen[s]) continue;
                seen[s] = true;
                int top = 0;
                stackV[0] = s; stackI[0] = 0;
                while (top >= 0) {
                    int u = stackV[top];
                    List<Integer> out = adj.get(u);
                    if (stackI[top] < out.size()) {
                        int w = out.get(stackI[top]++);
                        if (!seen[w]) { seen[w] = true; top++; stackV[top] = w; stackI[top] = 0; }
                    } else {
                        top--;
                        order[ordLen++] = u;
                    }
                }
            }
            List<List<Integer>> radj = new ArrayList<>();
            for (int i = 0; i < size; i++) radj.add(new ArrayList<>());
            for (int u = 0; u < size; u++) for (int w : adj.get(u)) radj.get(w).add(u);
            int[] comp = new int[size];
            Arrays.fill(comp, -1);
            int c = 0;
            int[] st = new int[size];
            for (int k = size - 1; k >= 0; k--) {
                int s = order[k];
                if (comp[s] != -1) continue;
                comp[s] = c;
                int top = 0;
                st[0] = s;
                while (top >= 0) {
                    int u = st[top--];
                    for (int w : radj.get(u)) if (comp[w] == -1) { comp[w] = c; st[++top] = w; }
                }
                c++;
            }
            boolean[] res = new boolean[n];
            for (int v = 0; v < n; v++) {
                if (comp[2 * v] == comp[2 * v + 1]) return null;
                res[v] = comp[2 * v] > comp[2 * v + 1];
            }
            return res;
        }
    }

    static long rngState = 2463534242L;
    static int next(int k) {
        long x = rngState;
        x ^= (x << 13) & 0xFFFFFFFFL;
        x ^= x >>> 17;
        x ^= (x << 5) & 0xFFFFFFFFL;
        rngState = x;
        return (int) (x % k);
    }

    static boolean satisfies(boolean[] a, int[][] cl) {
        for (int[] c : cl) if (a[c[0]] != (c[1] == 1) && a[c[2]] != (c[3] == 1)) return false;
        return true;
    }

    static TwoSat build(int n, int[][] cl) {
        TwoSat ts = new TwoSat(n);
        for (int[] c : cl) ts.addClause(c[0], c[1] == 1, c[2], c[3] == 1);
        return ts;
    }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    public static void main(String[] args) {
        int[][] ex = {{0, 1, 1, 1}, {0, 0, 2, 1}, {1, 0, 2, 1}, {2, 0, 3, 1}, {3, 0, 0, 0}};
        check(Arrays.equals(build(4, ex).solve(), new boolean[]{false, true, true, true}), "example");
        int[][] unsat = {{0, 1, 1, 1}, {0, 1, 1, 0}, {0, 0, 1, 1}, {0, 0, 1, 0}};
        check(build(2, unsat).solve() == null, "unsat");

        TwoSat ts = new TwoSat(3);
        ts.xor(0, 1); ts.equal(1, 2); ts.force(0, true);
        check(Arrays.equals(ts.solve(), new boolean[]{true, false, false}), "helpers");
        ts = new TwoSat(3);
        ts.atMostOne(new int[]{0, 1, 2}); ts.force(1, true); ts.implies(1, true, 0, false);
        check(Arrays.equals(ts.solve(), new boolean[]{false, true, false}), "at most one");

        for (int t = 0; t < 300; t++) {
            int n = 1 + next(5), m = 1 + next(8);
            int[][] cl = new int[m][];
            for (int i = 0; i < m; i++) cl[i] = new int[]{next(n), next(2), next(n), next(2)};
            boolean brute = false;
            for (int mask = 0; mask < (1 << n) && !brute; mask++) {
                boolean[] a = new boolean[n];
                for (int v = 0; v < n; v++) a[v] = ((mask >> v) & 1) == 1;
                brute = satisfies(a, cl);
            }
            boolean[] got = build(n, cl).solve();
            check((got != null) == brute, "random sat/unsat");
            if (got != null) check(satisfies(got, cl), "random assignment");
        }
        System.out.println("2-SAT: all tests passed");
    }
}
#include <cstdint>
#include <iostream>
#include <optional>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

struct TwoSat {
    int n;
    std::vector<std::vector<int>> adj;
    explicit TwoSat(int n) : n(n), adj(2 * n) {}

    static int lit(int v, bool value) { return value ? 2 * v : 2 * v + 1; }

    // Require (x_a == va) OR (x_b == vb).
    void add_clause(int a, bool va, int b, bool vb) {
        int la = lit(a, va), lb = lit(b, vb);
        adj[la ^ 1].push_back(lb);
        adj[lb ^ 1].push_back(la);
    }
    void force(int a, bool va) { add_clause(a, va, a, va); }
    void implies(int a, bool va, int b, bool vb) { add_clause(a, !va, b, vb); }
    void xor_(int a, int b) { add_clause(a, true, b, true); add_clause(a, false, b, false); }
    void equal(int a, int b) { add_clause(a, true, b, false); add_clause(a, false, b, true); }
    void at_most_one(const std::vector<int>& vs) {
        for (size_t i = 0; i < vs.size(); ++i)
            for (size_t j = i + 1; j < vs.size(); ++j) add_clause(vs[i], false, vs[j], false);
    }

    std::optional<std::vector<bool>> solve() const {
        int size = 2 * n;
        std::vector<int> order;
        order.reserve(size);
        std::vector<char> seen(size, 0);
        std::vector<std::pair<int, size_t>> stack;
        for (int s = 0; s < size; ++s) {
            if (seen[s]) continue;
            seen[s] = 1;
            stack.push_back({s, 0});
            while (!stack.empty()) {
                auto& [u, i] = stack.back();
                if (i < adj[u].size()) {
                    int w = adj[u][i++];
                    if (!seen[w]) { seen[w] = 1; stack.push_back({w, 0}); }
                } else {
                    order.push_back(u);
                    stack.pop_back();
                }
            }
        }
        std::vector<std::vector<int>> radj(size);
        for (int u = 0; u < size; ++u)
            for (int w : adj[u]) radj[w].push_back(u);
        std::vector<int> comp(size, -1), st;
        int c = 0;
        for (int k = size - 1; k >= 0; --k) {
            int s = order[k];
            if (comp[s] != -1) continue;
            comp[s] = c;
            st.push_back(s);
            while (!st.empty()) {
                int u = st.back();
                st.pop_back();
                for (int w : radj[u])
                    if (comp[w] == -1) { comp[w] = c; st.push_back(w); }
            }
            ++c;
        }
        std::vector<bool> res(n);
        for (int v = 0; v < n; ++v) {
            if (comp[2 * v] == comp[2 * v + 1]) return std::nullopt;
            res[v] = comp[2 * v] > comp[2 * v + 1];
        }
        return res;
    }
};

struct Clause { int a; bool va; int b; bool vb; };

static uint32_t rng_state = 2463534242u;
int next_int(int k) {
    uint32_t x = rng_state;
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    rng_state = x;
    return static_cast<int>(x % static_cast<uint32_t>(k));
}

bool satisfies(const std::vector<bool>& a, const std::vector<Clause>& cl) {
    for (const auto& c : cl)
        if (a[c.a] != c.va && a[c.b] != c.vb) return false;
    return true;
}

TwoSat build(int n, const std::vector<Clause>& cl) {
    TwoSat ts(n);
    for (const auto& c : cl) ts.add_clause(c.a, c.va, c.b, c.vb);
    return ts;
}

void check(bool ok, const std::string& msg) { if (!ok) throw std::runtime_error(msg); }

int main() {
    std::vector<Clause> ex = {{0, true, 1, true}, {0, false, 2, true}, {1, false, 2, true},
                              {2, false, 3, true}, {3, false, 0, false}};
    auto r = build(4, ex).solve();
    check(r && *r == std::vector<bool>{false, true, true, true}, "example");
    std::vector<Clause> unsat = {{0, true, 1, true}, {0, true, 1, false}, {0, false, 1, true}, {0, false, 1, false}};
    check(!build(2, unsat).solve(), "unsat");

    TwoSat ts(3);
    ts.xor_(0, 1); ts.equal(1, 2); ts.force(0, true);
    r = ts.solve();
    check(r && *r == std::vector<bool>{true, false, false}, "helpers");
    TwoSat ts2(3);
    ts2.at_most_one({0, 1, 2}); ts2.force(1, true); ts2.implies(1, true, 0, false);
    r = ts2.solve();
    check(r && *r == std::vector<bool>{false, true, false}, "at most one");

    for (int t = 0; t < 300; ++t) {
        int n = 1 + next_int(5), m = 1 + next_int(8);
        std::vector<Clause> cl;
        for (int i = 0; i < m; ++i) {
            int a = next_int(n); bool va = next_int(2) == 1;
            int b = next_int(n); bool vb = next_int(2) == 1;
            cl.push_back({a, va, b, vb});
        }
        bool brute = false;
        for (int mask = 0; mask < (1 << n) && !brute; ++mask) {
            std::vector<bool> a(n);
            for (int v = 0; v < n; ++v) a[v] = (mask >> v) & 1;
            brute = satisfies(a, cl);
        }
        auto got = build(n, cl).solve();
        check(got.has_value() == brute, "random sat/unsat");
        if (got) check(satisfies(*got, cl), "random assignment");
    }
    std::cout << "2-SAT: all tests passed\n";
}
class TwoSat {
  n: number;
  adj: number[][];

  constructor(n: number) {
    this.n = n;
    this.adj = Array.from({ length: 2 * n }, () => [] as number[]);
  }

  static lit(v: number, value: boolean): number {
    return value ? 2 * v : 2 * v + 1;
  }

  /** Require (x_a == va) OR (x_b == vb). */
  addClause(a: number, va: boolean, b: number, vb: boolean): void {
    const la = TwoSat.lit(a, va), lb = TwoSat.lit(b, vb);
    this.adj[la ^ 1].push(lb);
    this.adj[lb ^ 1].push(la);
  }
  force(a: number, va: boolean): void { this.addClause(a, va, a, va); }
  implies(a: number, va: boolean, b: number, vb: boolean): void { this.addClause(a, !va, b, vb); }
  xor(a: number, b: number): void { this.addClause(a, true, b, true); this.addClause(a, false, b, false); }
  equal(a: number, b: number): void { this.addClause(a, true, b, false); this.addClause(a, false, b, true); }
  atMostOne(vs: number[]): void {
    for (let i = 0; i < vs.length; i++)
      for (let j = i + 1; j < vs.length; j++) this.addClause(vs[i], false, vs[j], false);
  }

  solve(): boolean[] | null {
    const size = 2 * this.n, adj = this.adj;
    const order: number[] = [];
    const seen = new Array<boolean>(size).fill(false);
    for (let s = 0; s < size; s++) {
      if (seen[s]) continue;
      seen[s] = true;
      const stack: [number, number][] = [[s, 0]];
      while (stack.length > 0) {
        const top = stack[stack.length - 1];
        const u = top[0];
        if (top[1] < adj[u].length) {
          const w = adj[u][top[1]++];
          if (!seen[w]) { seen[w] = true; stack.push([w, 0]); }
        } else {
          stack.pop();
          order.push(u);
        }
      }
    }
    const radj: number[][] = Array.from({ length: size }, () => [] as number[]);
    for (let u = 0; u < size; u++) for (const w of adj[u]) radj[w].push(u);
    const comp = new Array<number>(size).fill(-1);
    let c = 0;
    for (let k = size - 1; k >= 0; k--) {
      const s = order[k];
      if (comp[s] !== -1) continue;
      comp[s] = c;
      const st = [s];
      while (st.length > 0) {
        const u = st.pop()!;
        for (const w of radj[u]) if (comp[w] === -1) { comp[w] = c; st.push(w); }
      }
      c++;
    }
    const res: boolean[] = [];
    for (let v = 0; v < this.n; v++) {
      if (comp[2 * v] === comp[2 * v + 1]) return null;
      res.push(comp[2 * v] > comp[2 * v + 1]);
    }
    return res;
  }
}

type Clause = [number, boolean, number, boolean];

let rngState = 2463534242;
function nextInt(k: number): number {
  let x = rngState;
  x = (x ^ (x << 13)) >>> 0;
  x = (x ^ (x >>> 17)) >>> 0;
  x = (x ^ (x << 5)) >>> 0;
  rngState = x;
  return x % k;
}

function satisfies(a: boolean[], cl: Clause[]): boolean {
  return cl.every(([x, vx, y, vy]) => a[x] === vx || a[y] === vy);
}

function build(n: number, cl: Clause[]): TwoSat {
  const ts = new TwoSat(n);
  for (const [a, va, b, vb] of cl) ts.addClause(a, va, b, vb);
  return ts;
}

function check(ok: boolean, msg: string): void {
  if (!ok) throw new Error(msg);
}

const same = (x: boolean[] | null, y: boolean[]): boolean =>
  x !== null && x.length === y.length && x.every((v, i) => v === y[i]);

const ex: Clause[] = [[0, true, 1, true], [0, false, 2, true], [1, false, 2, true], [2, false, 3, true], [3, false, 0, false]];
check(same(build(4, ex).solve(), [false, true, true, true]), "example");
const unsat: Clause[] = [[0, true, 1, true], [0, true, 1, false], [0, false, 1, true], [0, false, 1, false]];
check(build(2, unsat).solve() === null, "unsat");

let ts = new TwoSat(3);
ts.xor(0, 1); ts.equal(1, 2); ts.force(0, true);
check(same(ts.solve(), [true, false, false]), "helpers");
ts = new TwoSat(3);
ts.atMostOne([0, 1, 2]); ts.force(1, true); ts.implies(1, true, 0, false);
check(same(ts.solve(), [false, true, false]), "at most one");

for (let t = 0; t < 300; t++) {
  const n = 1 + nextInt(5), m = 1 + nextInt(8);
  const cl: Clause[] = [];
  for (let i = 0; i < m; i++) {
    const a = nextInt(n), va = nextInt(2) === 1, b = nextInt(n), vb = nextInt(2) === 1;
    cl.push([a, va, b, vb]);
  }
  let brute = false;
  for (let mask = 0; mask < (1 << n) && !brute; mask++) {
    const a = Array.from({ length: n }, (_, v) => ((mask >> v) & 1) === 1);
    brute = satisfies(a, cl);
  }
  const got = build(n, cl).solve();
  check((got !== null) === brute, "random sat/unsat");
  if (got !== null) check(satisfies(got, cl), "random assignment");
}
console.log("2-SAT: all tests passed");

Note that add_clause with the same literal twice is how you force a value: it adds the single edge , so can never be chosen.

Colouring: greedy, Welsh–Powell, DSATUR and the exact chromatic number

The exact function uses inclusion–exclusion; the subset DP is included as a cross-check. Python uses exact integers; the other three reduce modulo (see the complexity note).

def greedy_colouring(adj: list[list[int]], order: list[int]) -> list[int]:
    col = [-1] * len(adj)
    for v in order:
        used = {col[w] for w in adj[v] if col[w] != -1}
        c = 0
        while c in used:
            c += 1
        col[v] = c
    return col


def welsh_powell(adj: list[list[int]]) -> list[int]:
    order = sorted(range(len(adj)), key=lambda v: (-len(adj[v]), v))
    return greedy_colouring(adj, order)


def dsatur(adj: list[list[int]]) -> list[int]:
    n = len(adj)
    col = [-1] * n
    for _ in range(n):
        best, best_key = -1, (-1, -1)
        for v in range(n):
            if col[v] != -1:
                continue
            sat = len({col[w] for w in adj[v] if col[w] != -1})
            unc = sum(1 for w in adj[v] if col[w] == -1)
            if (sat, unc) > best_key:  # strict: ties keep the lowest index
                best, best_key = v, (sat, unc)
        used = {col[w] for w in adj[best] if col[w] != -1}
        c = 0
        while c in used:
            c += 1
        col[best] = c
    return col


def is_proper(adj: list[list[int]], col: list[int]) -> bool:
    return all(col[u] != col[w] for u in range(len(adj)) for w in adj[u])


def chromatic_number(adj: list[list[int]]) -> int:
    """Inclusion-exclusion, O(2^n * n). Exact big integers."""
    n = len(adj)
    if n == 0:
        return 0
    nb = [sum(1 << w for w in adj[v]) for v in range(n)]
    full = 1 << n
    ind = [0] * full  # ind[S] = number of independent subsets of S, empty set included
    ind[0] = 1
    for s in range(1, full):
        v = (s & -s).bit_length() - 1
        rest = s & ~(1 << v)
        ind[s] = ind[rest] + ind[rest & ~nb[v]]
    sign = [1 if (n - s.bit_count()) % 2 == 0 else -1 for s in range(full)]
    power = [1] * full
    for k in range(1, n + 1):
        total = 0
        for s in range(full):
            power[s] *= ind[s]
            total += sign[s] * power[s]
        if total > 0:
            return k
    return n


def chromatic_number_3n(adj: list[list[int]]) -> int:
    """Subset DP, O(3^n)."""
    n = len(adj)
    nb = [sum(1 << w for w in adj[v]) for v in range(n)]
    full = 1 << n
    indep = [False] * full
    indep[0] = True
    for s in range(1, full):
        v = (s & -s).bit_length() - 1
        rest = s & ~(1 << v)
        indep[s] = indep[rest] and (nb[v] & rest) == 0
    f = [0] * full
    for s in range(1, full):
        low = s & -s
        best = n
        t = s
        while t:
            if t & low and indep[t]:  # the class containing the lowest vertex
                best = min(best, f[s ^ t] + 1)
            t = (t - 1) & s
        f[s] = best
    return f[full - 1]


def from_edges(n: int, edges: list[tuple[int, int]]) -> list[list[int]]:
    adj: list[list[int]] = [[] for _ in range(n)]
    for u, w in edges:
        adj[u].append(w)
        adj[w].append(u)
    return adj


def num_colours(col: list[int]) -> int:
    return max(col) + 1 if col else 0


if __name__ == "__main__":
    g6 = from_edges(6, [(0, 1), (0, 2), (0, 3), (1, 2), (1, 4), (2, 3), (2, 4), (3, 5), (4, 5)])
    assert greedy_colouring(g6, list(range(6))) == [0, 1, 2, 1, 0, 2]
    assert dsatur(g6) == [1, 2, 0, 2, 1, 0]
    assert welsh_powell(g6) == dsatur(g6)
    assert chromatic_number(g6) == 3 == chromatic_number_3n(g6)

    k = 4  # crown graph: a_i = i, b_i = k + i, a_i -- b_j for i != j
    crown = from_edges(2 * k, [(i, k + j) for i in range(k) for j in range(k) if i != j])
    bad_order = [v for i in range(k) for v in (i, k + i)]
    assert num_colours(greedy_colouring(crown, bad_order)) == k
    assert num_colours(dsatur(crown)) == 2
    assert chromatic_number(crown) == 2 == chromatic_number_3n(crown)

    c5 = from_edges(5, [(i, (i + 1) % 5) for i in range(5)])
    k4 = from_edges(4, [(i, j) for i in range(4) for j in range(i + 1, 4)])
    petersen = from_edges(10, [(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
                          + [(5 + i, 5 + (i + 2) % 5) for i in range(5)])
    empty3 = from_edges(3, [])
    for g, chi in [(c5, 3), (k4, 4), (petersen, 3), (empty3, 1), (g6, 3), (crown, 2)]:
        assert chromatic_number(g) == chi == chromatic_number_3n(g)
        for col in (greedy_colouring(g, list(range(len(g)))), welsh_powell(g), dsatur(g)):
            assert is_proper(g, col)
            assert chi <= num_colours(col) <= max(len(a) for a in g) + 1
    print("colouring: all tests passed")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.IntStream;

public class ColouringDemo {
    static final long P = 1_000_000_007L;

    static int[] greedy(List<List<Integer>> adj, int[] order) {
        int n = adj.size();
        int[] col = new int[n];
        Arrays.fill(col, -1);
        boolean[] used = new boolean[n + 1];
        for (int v : order) {
            for (int w : adj.get(v)) if (col[w] != -1) used[col[w]] = true;
            int c = 0;
            while (used[c]) c++;
            col[v] = c;
            for (int w : adj.get(v)) if (col[w] != -1) used[col[w]] = false;
        }
        return col;
    }

    static int[] welshPowell(List<List<Integer>> adj) {
        int[] order = IntStream.range(0, adj.size()).boxed()
                .sorted(Comparator.<Integer>comparingInt(v -> -adj.get(v).size()).thenComparingInt(v -> v))
                .mapToInt(Integer::intValue).toArray();
        return greedy(adj, order);
    }

    static int[] dsatur(List<List<Integer>> adj) {
        int n = adj.size();
        int[] col = new int[n];
        Arrays.fill(col, -1);
        for (int step = 0; step < n; step++) {
            int best = -1, bestSat = -1, bestUnc = -1;
            for (int v = 0; v < n; v++) {
                if (col[v] != -1) continue;
                boolean[] seen = new boolean[n + 1];
                int sat = 0, unc = 0;
                for (int w : adj.get(v)) {
                    if (col[w] == -1) unc++;
                    else if (!seen[col[w]]) { seen[col[w]] = true; sat++; }
                }
                if (sat > bestSat || (sat == bestSat && unc > bestUnc)) { best = v; bestSat = sat; bestUnc = unc; }
            }
            boolean[] used = new boolean[n + 1];
            for (int w : adj.get(best)) if (col[w] != -1) used[col[w]] = true;
            int c = 0;
            while (used[c]) c++;
            col[best] = c;
        }
        return col;
    }

    static boolean isProper(List<List<Integer>> adj, int[] col) {
        for (int u = 0; u < adj.size(); u++) for (int w : adj.get(u)) if (col[u] == col[w]) return false;
        return true;
    }

    static int[] masks(List<List<Integer>> adj) {
        int[] nb = new int[adj.size()];
        for (int v = 0; v < adj.size(); v++) for (int w : adj.get(v)) nb[v] |= 1 << w;
        return nb;
    }

    /** Inclusion-exclusion modulo P, O(2^n * n). */
    static int chromaticNumber(List<List<Integer>> adj) {
        int n = adj.size();
        if (n == 0) return 0;
        int[] nb = masks(adj);
        int full = 1 << n;
        long[] ind = new long[full];
        ind[0] = 1;
        for (int s = 1; s < full; s++) {
            int v = Integer.numberOfTrailingZeros(s);
            int rest = s & ~(1 << v);
            ind[s] = (ind[rest] + ind[rest & ~nb[v]]) % P;
        }
        long[] power = new long[full];
        Arrays.fill(power, 1);
        for (int k = 1; k <= n; k++) {
            long total = 0;
            for (int s = 0; s < full; s++) {
                power[s] = power[s] * ind[s] % P;
                if (((n - Integer.bitCount(s)) & 1) == 0) total += power[s];
                else total += P - power[s];
            }
            if (total % P != 0) return k;
        }
        return n;
    }

    /** Subset DP, O(3^n). */
    static int chromaticNumber3n(List<List<Integer>> adj) {
        int n = adj.size();
        int[] nb = masks(adj);
        int full = 1 << n;
        boolean[] indep = new boolean[full];
        indep[0] = true;
        for (int s = 1; s < full; s++) {
            int v = Integer.numberOfTrailingZeros(s);
            int rest = s & ~(1 << v);
            indep[s] = indep[rest] && (nb[v] & rest) == 0;
        }
        int[] f = new int[full];
        for (int s = 1; s < full; s++) {
            int low = s & -s, best = n;
            for (int t = s; t > 0; t = (t - 1) & s)
                if ((t & low) != 0 && indep[t]) best = Math.min(best, f[s ^ t] + 1);
            f[s] = best;
        }
        return f[full - 1];
    }

    static List<List<Integer>> fromEdges(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        return adj;
    }

    static int numColours(int[] col) { return Arrays.stream(col).max().orElse(-1) + 1; }
    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    public static void main(String[] args) {
        var g6 = fromEdges(6, new int[][]{{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 4}, {2, 3}, {2, 4}, {3, 5}, {4, 5}});
        check(Arrays.equals(greedy(g6, new int[]{0, 1, 2, 3, 4, 5}), new int[]{0, 1, 2, 1, 0, 2}), "greedy g6");
        check(Arrays.equals(dsatur(g6), new int[]{1, 2, 0, 2, 1, 0}), "dsatur g6");
        check(Arrays.equals(welshPowell(g6), dsatur(g6)), "welsh-powell g6");
        check(chromaticNumber(g6) == 3 && chromaticNumber3n(g6) == 3, "chi g6");

        int k = 4;
        List<int[]> ce = new ArrayList<>();
        for (int i = 0; i < k; i++) for (int j = 0; j < k; j++) if (i != j) ce.add(new int[]{i, k + j});
        var crown = fromEdges(2 * k, ce.toArray(new int[0][]));
        int[] bad = new int[2 * k];
        for (int i = 0; i < k; i++) { bad[2 * i] = i; bad[2 * i + 1] = k + i; }
        check(numColours(greedy(crown, bad)) == k, "crown greedy");
        check(numColours(dsatur(crown)) == 2, "crown dsatur");

        List<int[]> pe = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            pe.add(new int[]{i, (i + 1) % 5});
            pe.add(new int[]{i, i + 5});
            pe.add(new int[]{5 + i, 5 + (i + 2) % 5});
        }
        List<int[]> c5e = new ArrayList<>(), k4e = new ArrayList<>();
        for (int i = 0; i < 5; i++) c5e.add(new int[]{i, (i + 1) % 5});
        for (int i = 0; i < 4; i++) for (int j = i + 1; j < 4; j++) k4e.add(new int[]{i, j});
        Object[][] cases = {
            {fromEdges(5, c5e.toArray(new int[0][])), 3}, {fromEdges(4, k4e.toArray(new int[0][])), 4},
            {fromEdges(10, pe.toArray(new int[0][])), 3}, {fromEdges(3, new int[0][]), 1}, {g6, 3}, {crown, 2}};
        for (Object[] cs : cases) {
            @SuppressWarnings("unchecked") List<List<Integer>> g = (List<List<Integer>>) cs[0];
            int chi = (Integer) cs[1];
            check(chromaticNumber(g) == chi && chromaticNumber3n(g) == chi, "chi");
            int maxDeg = g.stream().mapToInt(List::size).max().orElse(0);
            int[] natural = IntStream.range(0, g.size()).toArray();
            for (int[] col : new int[][]{greedy(g, natural), welshPowell(g), dsatur(g)}) {
                check(isProper(g, col), "proper");
                check(chi <= numColours(col) && numColours(col) <= maxDeg + 1, "bounds");
            }
        }
        System.out.println("colouring: all tests passed");
    }
}
#include <algorithm>
#include <bit>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

using Graph = std::vector<std::vector<int>>;
constexpr uint64_t P = 1'000'000'007ULL;

std::vector<int> greedy(const Graph& adj, const std::vector<int>& order) {
    int n = static_cast<int>(adj.size());
    std::vector<int> col(n, -1);
    std::vector<char> used(n + 1, 0);
    for (int v : order) {
        for (int w : adj[v]) if (col[w] != -1) used[col[w]] = 1;
        int c = 0;
        while (used[c]) ++c;
        col[v] = c;
        for (int w : adj[v]) if (col[w] != -1) used[col[w]] = 0;
    }
    return col;
}

std::vector<int> welsh_powell(const Graph& adj) {
    std::vector<int> order(adj.size());
    std::iota(order.begin(), order.end(), 0);
    std::stable_sort(order.begin(), order.end(),
                     [&](int a, int b) { return adj[a].size() > adj[b].size(); });
    return greedy(adj, order);
}

std::vector<int> dsatur(const Graph& adj) {
    int n = static_cast<int>(adj.size());
    std::vector<int> col(n, -1);
    for (int step = 0; step < n; ++step) {
        int best = -1, best_sat = -1, best_unc = -1;
        for (int v = 0; v < n; ++v) {
            if (col[v] != -1) continue;
            std::set<int> s;
            int unc = 0;
            for (int w : adj[v]) { if (col[w] == -1) ++unc; else s.insert(col[w]); }
            int sat = static_cast<int>(s.size());
            if (sat > best_sat || (sat == best_sat && unc > best_unc)) { best = v; best_sat = sat; best_unc = unc; }
        }
        std::vector<char> used(n + 1, 0);
        for (int w : adj[best]) if (col[w] != -1) used[col[w]] = 1;
        int c = 0;
        while (used[c]) ++c;
        col[best] = c;
    }
    return col;
}

bool is_proper(const Graph& adj, const std::vector<int>& col) {
    for (size_t u = 0; u < adj.size(); ++u)
        for (int w : adj[u]) if (col[u] == col[w]) return false;
    return true;
}

std::vector<uint32_t> masks(const Graph& adj) {
    std::vector<uint32_t> nb(adj.size(), 0);
    for (size_t v = 0; v < adj.size(); ++v) for (int w : adj[v]) nb[v] |= 1u << w;
    return nb;
}

// Inclusion-exclusion modulo P, O(2^n * n).
int chromatic_number(const Graph& adj) {
    int n = static_cast<int>(adj.size());
    if (n == 0) return 0;
    auto nb = masks(adj);
    uint32_t full = 1u << n;
    std::vector<uint64_t> ind(full), power(full, 1);
    ind[0] = 1;
    for (uint32_t s = 1; s < full; ++s) {
        int v = std::countr_zero(s);
        uint32_t rest = s & ~(1u << v);
        ind[s] = (ind[rest] + ind[rest & ~nb[v]]) % P;
    }
    for (int k = 1; k <= n; ++k) {
        uint64_t total = 0;
        for (uint32_t s = 0; s < full; ++s) {
            power[s] = power[s] * ind[s] % P;
            total += ((n - std::popcount(s)) % 2 == 0) ? power[s] : P - power[s];
            total %= P;
        }
        if (total != 0) return k;
    }
    return n;
}

// Subset DP, O(3^n).
int chromatic_number_3n(const Graph& adj) {
    int n = static_cast<int>(adj.size());
    auto nb = masks(adj);
    uint32_t full = 1u << n;
    std::vector<char> indep(full, 0);
    indep[0] = 1;
    for (uint32_t s = 1; s < full; ++s) {
        int v = std::countr_zero(s);
        uint32_t rest = s & ~(1u << v);
        indep[s] = indep[rest] && (nb[v] & rest) == 0;
    }
    std::vector<int> f(full, 0);
    for (uint32_t s = 1; s < full; ++s) {
        uint32_t low = s & (~s + 1);
        int best = n;
        for (uint32_t t = s; t; t = (t - 1) & s)
            if ((t & low) && indep[t]) best = std::min(best, f[s ^ t] + 1);
        f[s] = best;
    }
    return f[full - 1];
}

Graph from_edges(int n, const std::vector<std::pair<int, int>>& edges) {
    Graph adj(n);
    for (auto [u, w] : edges) { adj[u].push_back(w); adj[w].push_back(u); }
    return adj;
}

int num_colours(const std::vector<int>& col) {
    return col.empty() ? 0 : *std::max_element(col.begin(), col.end()) + 1;
}

void check(bool ok, const std::string& msg) { if (!ok) throw std::runtime_error(msg); }

int main() {
    Graph g6 = from_edges(6, {{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 4}, {2, 3}, {2, 4}, {3, 5}, {4, 5}});
    check(greedy(g6, {0, 1, 2, 3, 4, 5}) == std::vector<int>{0, 1, 2, 1, 0, 2}, "greedy g6");
    check(dsatur(g6) == std::vector<int>{1, 2, 0, 2, 1, 0}, "dsatur g6");
    check(welsh_powell(g6) == dsatur(g6), "welsh-powell g6");
    check(chromatic_number(g6) == 3 && chromatic_number_3n(g6) == 3, "chi g6");

    const int k = 4;
    std::vector<std::pair<int, int>> ce;
    for (int i = 0; i < k; ++i) for (int j = 0; j < k; ++j) if (i != j) ce.push_back({i, k + j});
    Graph crown = from_edges(2 * k, ce);
    std::vector<int> bad;
    for (int i = 0; i < k; ++i) { bad.push_back(i); bad.push_back(k + i); }
    check(num_colours(greedy(crown, bad)) == k, "crown greedy");
    check(num_colours(dsatur(crown)) == 2, "crown dsatur");

    std::vector<std::pair<int, int>> pe, c5e, k4e;
    for (int i = 0; i < 5; ++i) {
        pe.push_back({i, (i + 1) % 5});
        pe.push_back({i, i + 5});
        pe.push_back({5 + i, 5 + (i + 2) % 5});
        c5e.push_back({i, (i + 1) % 5});
    }
    for (int i = 0; i < 4; ++i) for (int j = i + 1; j < 4; ++j) k4e.push_back({i, j});
    std::vector<std::pair<Graph, int>> cases = {{from_edges(5, c5e), 3}, {from_edges(4, k4e), 4},
        {from_edges(10, pe), 3}, {from_edges(3, {}), 1}, {g6, 3}, {crown, 2}};
    for (const auto& [g, chi] : cases) {
        check(chromatic_number(g) == chi && chromatic_number_3n(g) == chi, "chi");
        size_t max_deg = 0;
        for (const auto& a : g) max_deg = std::max(max_deg, a.size());
        std::vector<int> natural(g.size());
        std::iota(natural.begin(), natural.end(), 0);
        for (const auto& col : {greedy(g, natural), welsh_powell(g), dsatur(g)}) {
            check(is_proper(g, col), "proper");
            check(chi <= num_colours(col) && num_colours(col) <= static_cast<int>(max_deg) + 1, "bounds");
        }
    }
    std::cout << "colouring: all tests passed\n";
}
type Graph = number[][];
const P = 1_000_000_007;

function mulmod(a: number, b: number, m: number): number {
  // split b into 16-bit halves so every partial product stays below 2^53
  const hi = Math.floor(b / 65536), lo = b % 65536;
  return (((a * hi) % m) * 65536 + a * lo) % m;
}

function popcount(x: number): number {
  let c = 0;
  while (x) { x &= x - 1; c++; }
  return c;
}

function ctz(x: number): number {
  return 31 - Math.clz32(x & -x);
}

function greedy(adj: Graph, order: number[]): number[] {
  const col = new Array<number>(adj.length).fill(-1);
  for (const v of order) {
    const used = new Set<number>();
    for (const w of adj[v]) if (col[w] !== -1) used.add(col[w]);
    let c = 0;
    while (used.has(c)) c++;
    col[v] = c;
  }
  return col;
}

function welshPowell(adj: Graph): number[] {
  const order = adj.map((_, v) => v).sort((a, b) => adj[b].length - adj[a].length || a - b);
  return greedy(adj, order);
}

function dsatur(adj: Graph): number[] {
  const n = adj.length;
  const col = new Array<number>(n).fill(-1);
  for (let step = 0; step < n; step++) {
    let best = -1, bestSat = -1, bestUnc = -1;
    for (let v = 0; v < n; v++) {
      if (col[v] !== -1) continue;
      const s = new Set<number>();
      let unc = 0;
      for (const w of adj[v]) { if (col[w] === -1) unc++; else s.add(col[w]); }
      if (s.size > bestSat || (s.size === bestSat && unc > bestUnc)) { best = v; bestSat = s.size; bestUnc = unc; }
    }
    const used = new Set<number>();
    for (const w of adj[best]) if (col[w] !== -1) used.add(col[w]);
    let c = 0;
    while (used.has(c)) c++;
    col[best] = c;
  }
  return col;
}

function isProper(adj: Graph, col: number[]): boolean {
  return adj.every((ws, u) => ws.every((w) => col[u] !== col[w]));
}

function masks(adj: Graph): number[] {
  return adj.map((ws) => ws.reduce((m, w) => m | (1 << w), 0));
}

/** Inclusion-exclusion modulo P, O(2^n * n). */
function chromaticNumber(adj: Graph): number {
  const n = adj.length;
  if (n === 0) return 0;
  const nb = masks(adj), full = 1 << n;
  const ind = new Array<number>(full).fill(0);
  ind[0] = 1;
  for (let s = 1; s < full; s++) {
    const v = ctz(s), rest = s & ~(1 << v);
    ind[s] = (ind[rest] + ind[rest & ~nb[v]]) % P;
  }
  const power = new Array<number>(full).fill(1);
  for (let k = 1; k <= n; k++) {
    let total = 0;
    for (let s = 0; s < full; s++) {
      power[s] = mulmod(power[s], ind[s], P);
      total = (total + ((n - popcount(s)) % 2 === 0 ? power[s] : P - power[s])) % P;
    }
    if (total !== 0) return k;
  }
  return n;
}

/** Subset DP, O(3^n). */
function chromaticNumber3n(adj: Graph): number {
  const n = adj.length, nb = masks(adj), full = 1 << n;
  const indep = new Array<boolean>(full).fill(false);
  indep[0] = true;
  for (let s = 1; s < full; s++) {
    const v = ctz(s), rest = s & ~(1 << v);
    indep[s] = indep[rest] && (nb[v] & rest) === 0;
  }
  const f = new Array<number>(full).fill(0);
  for (let s = 1; s < full; s++) {
    const low = s & -s;
    let best = n;
    for (let t = s; t > 0; t = (t - 1) & s) if (t & low && indep[t]) best = Math.min(best, f[s ^ t] + 1);
    f[s] = best;
  }
  return f[full - 1];
}

function fromEdges(n: number, edges: [number, number][]): Graph {
  const adj: Graph = Array.from({ length: n }, () => [] as number[]);
  for (const [u, w] of edges) { adj[u].push(w); adj[w].push(u); }
  return adj;
}

const numColours = (col: number[]): number => (col.length ? Math.max(...col) + 1 : 0);
const eq = (a: number[], b: number[]): boolean => a.length === b.length && a.every((x, i) => x === b[i]);
function check(ok: boolean, msg: string): void { if (!ok) throw new Error(msg); }

const g6 = fromEdges(6, [[0, 1], [0, 2], [0, 3], [1, 2], [1, 4], [2, 3], [2, 4], [3, 5], [4, 5]]);
check(eq(greedy(g6, [0, 1, 2, 3, 4, 5]), [0, 1, 2, 1, 0, 2]), "greedy g6");
check(eq(dsatur(g6), [1, 2, 0, 2, 1, 0]), "dsatur g6");
check(eq(welshPowell(g6), dsatur(g6)), "welsh-powell g6");
check(chromaticNumber(g6) === 3 && chromaticNumber3n(g6) === 3, "chi g6");

const k = 4;
const ce: [number, number][] = [];
for (let i = 0; i < k; i++) for (let j = 0; j < k; j++) if (i !== j) ce.push([i, k + j]);
const crown = fromEdges(2 * k, ce);
const bad: number[] = [];
for (let i = 0; i < k; i++) bad.push(i, k + i);
check(numColours(greedy(crown, bad)) === k, "crown greedy");
check(numColours(dsatur(crown)) === 2, "crown dsatur");

const pe: [number, number][] = [], c5e: [number, number][] = [], k4e: [number, number][] = [];
for (let i = 0; i < 5; i++) {
  pe.push([i, (i + 1) % 5], [i, i + 5], [5 + i, 5 + ((i + 2) % 5)]);
  c5e.push([i, (i + 1) % 5]);
}
for (let i = 0; i < 4; i++) for (let j = i + 1; j < 4; j++) k4e.push([i, j]);
const cases: [Graph, number][] = [[fromEdges(5, c5e), 3], [fromEdges(4, k4e), 4], [fromEdges(10, pe), 3],
  [fromEdges(3, []), 1], [g6, 3], [crown, 2]];
for (const [g, chi] of cases) {
  check(chromaticNumber(g) === chi && chromaticNumber3n(g) === chi, "chi");
  const maxDeg = Math.max(...g.map((a) => a.length));
  for (const col of [greedy(g, g.map((_, v) => v)), welshPowell(g), dsatur(g)]) {
    check(isProper(g, col), "proper");
    check(chi <= numColours(col) && numColours(col) <= maxDeg + 1, "bounds");
  }
}
console.log("colouring: all tests passed");

Maximum clique, independent set and vertex cover

Bron–Kerbosch with Tomita pivoting over bitmasks (Python integers are unbounded; Java and C++ use 64-bit masks, TypeScript 32-bit, so or ). A maximum independent set is a maximum clique of the complement graph, and the minimum vertex cover is its complement, by the identity . Test graphs: the six-vertex graph above, (the Moon–Moser extremal graph, 27 maximal cliques) and the Petersen graph.

def bron_kerbosch(n: int, nb: list[int]) -> tuple[int, int, int]:
    """Return (size of a maximum clique, its vertex mask, number of maximal cliques)."""
    best_size, best_mask, count = 0, 0, 0

    def expand(r: int, size: int, p: int, x: int) -> None:
        nonlocal best_size, best_mask, count
        if p == 0 and x == 0:
            count += 1
            if size > best_size:
                best_size, best_mask = size, r
            return
        px = p | x
        pivot = max((u for u in range(n) if px >> u & 1), key=lambda u: (p & nb[u]).bit_count())
        candidates = p & ~nb[pivot]
        while candidates:
            v_bit = candidates & -candidates
            v = v_bit.bit_length() - 1
            expand(r | v_bit, size + 1, p & nb[v], x & nb[v])
            p &= ~v_bit
            x |= v_bit
            candidates &= ~v_bit

    expand(0, 0, (1 << n) - 1, 0)
    return best_size, best_mask, count


def masks(n: int, edges: list[tuple[int, int]]) -> list[int]:
    nb = [0] * n
    for u, w in edges:
        nb[u] |= 1 << w
        nb[w] |= 1 << u
    return nb


def complement(n: int, nb: list[int]) -> list[int]:
    full = (1 << n) - 1
    return [full & ~nb[v] & ~(1 << v) for v in range(n)]


def vertex_cover_2approx(n: int, edges: list[tuple[int, int]]) -> set[int]:
    matched = [False] * n
    cover: set[int] = set()
    for u, w in edges:
        if not matched[u] and not matched[w]:
            matched[u] = matched[w] = True
            cover.update((u, w))
    return cover


def is_clique(nb: list[int], mask: int) -> bool:
    vs = [v for v in range(len(nb)) if mask >> v & 1]
    return all(nb[a] >> b & 1 for i, a in enumerate(vs) for b in vs[i + 1:])


if __name__ == "__main__":
    e6 = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 4), (2, 3), (2, 4), (3, 5), (4, 5)]
    nb6 = masks(6, e6)
    size, mask, count = bron_kerbosch(6, nb6)
    assert (size, count) == (3, 5) and is_clique(nb6, mask)

    part = [v // 3 for v in range(9)]  # K_{3,3,3}
    ek = [(u, w) for u in range(9) for w in range(u + 1, 9) if part[u] != part[w]]
    size, mask, count = bron_kerbosch(9, masks(9, ek))
    assert (size, count) == (3, 27)

    ep = ([(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
          + [(5 + i, 5 + (i + 2) % 5) for i in range(5)])
    nbp = masks(10, ep)
    size, mask, count = bron_kerbosch(10, nbp)
    assert (size, count) == (2, 15)  # triangle-free: the maximal cliques are the 15 edges
    alpha, ind_mask, _ = bron_kerbosch(10, complement(10, nbp))
    assert alpha == 4 and is_clique(complement(10, nbp), ind_mask)
    min_cover = 10 - alpha  # = 6
    cover = vertex_cover_2approx(10, ep)
    assert all(u in cover or w in cover for u, w in ep)
    assert min_cover <= len(cover) <= 2 * min_cover
    print("cliques and covers: all tests passed")
import java.util.HashSet;
import java.util.Set;

public class CliqueDemo {
    static int n;
    static long[] nb;
    static int bestSize, count;
    static long bestMask;

    static void expand(long r, int size, long p, long x) {
        if (p == 0 && x == 0) {
            count++;
            if (size > bestSize) { bestSize = size; bestMask = r; }
            return;
        }
        long px = p | x;
        int pivot = -1, pivotScore = -1;
        for (long t = px; t != 0; t &= t - 1) {
            int u = Long.numberOfTrailingZeros(t);
            int score = Long.bitCount(p & nb[u]);
            if (score > pivotScore) { pivotScore = score; pivot = u; }
        }
        long candidates = p & ~nb[pivot];
        while (candidates != 0) {
            long vBit = candidates & -candidates;
            int v = Long.numberOfTrailingZeros(vBit);
            expand(r | vBit, size + 1, p & nb[v], x & nb[v]);
            p &= ~vBit;
            x |= vBit;
            candidates &= ~vBit;
        }
    }

    /** Returns {max clique size, number of maximal cliques}; bestMask holds a maximum clique. */
    static int[] bronKerbosch(int nn, long[] masks) {
        n = nn; nb = masks; bestSize = 0; count = 0; bestMask = 0;
        expand(0, 0, n == 64 ? -1L : (1L << n) - 1, 0);
        return new int[]{bestSize, count};
    }

    static long[] masks(int n, int[][] edges) {
        long[] m = new long[n];
        for (int[] e : edges) { m[e[0]] |= 1L << e[1]; m[e[1]] |= 1L << e[0]; }
        return m;
    }

    static long[] complement(int n, long[] m) {
        long full = (1L << n) - 1;
        long[] c = new long[n];
        for (int v = 0; v < n; v++) c[v] = full & ~m[v] & ~(1L << v);
        return c;
    }

    static boolean isClique(long[] m, long mask) {
        for (long a = mask; a != 0; a &= a - 1) {
            int u = Long.numberOfTrailingZeros(a);
            if ((m[u] | (1L << u) | ~mask) != -1L) return false;
        }
        return true;
    }

    static Set<Integer> vertexCover2Approx(int n, int[][] edges) {
        boolean[] matched = new boolean[n];
        Set<Integer> cover = new HashSet<>();
        for (int[] e : edges)
            if (!matched[e[0]] && !matched[e[1]]) {
                matched[e[0]] = matched[e[1]] = true;
                cover.add(e[0]); cover.add(e[1]);
            }
        return cover;
    }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    public static void main(String[] args) {
        int[][] e6 = {{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 4}, {2, 3}, {2, 4}, {3, 5}, {4, 5}};
        long[] nb6 = masks(6, e6);
        int[] r = bronKerbosch(6, nb6);
        check(r[0] == 3 && r[1] == 5 && isClique(nb6, bestMask), "g6");

        int[][] ek = new int[27][];
        int idx = 0;
        for (int u = 0; u < 9; u++) for (int w = u + 1; w < 9; w++) if (u / 3 != w / 3) ek[idx++] = new int[]{u, w};
        r = bronKerbosch(9, masks(9, ek));
        check(r[0] == 3 && r[1] == 27, "K333");

        int[][] ep = new int[15][];
        for (int i = 0; i < 5; i++) {
            ep[3 * i] = new int[]{i, (i + 1) % 5};
            ep[3 * i + 1] = new int[]{i, i + 5};
            ep[3 * i + 2] = new int[]{5 + i, 5 + (i + 2) % 5};
        }
        long[] nbp = masks(10, ep);
        r = bronKerbosch(10, nbp);
        check(r[0] == 2 && r[1] == 15, "petersen cliques");
        long[] comp = complement(10, nbp);
        r = bronKerbosch(10, comp);
        check(r[0] == 4 && isClique(comp, bestMask), "petersen alpha");
        int minCover = 10 - r[0];
        Set<Integer> cover = vertexCover2Approx(10, ep);
        for (int[] e : ep) check(cover.contains(e[0]) || cover.contains(e[1]), "is cover");
        check(minCover <= cover.size() && cover.size() <= 2 * minCover, "2-approx");
        System.out.println("cliques and covers: all tests passed");
    }
}
#include <bit>
#include <cstdint>
#include <functional>
#include <iostream>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

struct CliqueResult { int best_size; uint64_t best_mask; int count; };

CliqueResult bron_kerbosch(int n, const std::vector<uint64_t>& nb) {
    CliqueResult res{0, 0, 0};
    std::function<void(uint64_t, int, uint64_t, uint64_t)> expand =
        [&](uint64_t r, int size, uint64_t p, uint64_t x) {
            if (p == 0 && x == 0) {
                ++res.count;
                if (size > res.best_size) { res.best_size = size; res.best_mask = r; }
                return;
            }
            int pivot = -1, score = -1;
            for (uint64_t t = p | x; t; t &= t - 1) {
                int u = std::countr_zero(t);
                int s = std::popcount(p & nb[u]);
                if (s > score) { score = s; pivot = u; }
            }
            uint64_t candidates = p & ~nb[pivot];
            while (candidates) {
                uint64_t v_bit = candidates & (~candidates + 1);
                int v = std::countr_zero(v_bit);
                expand(r | v_bit, size + 1, p & nb[v], x & nb[v]);
                p &= ~v_bit;
                x |= v_bit;
                candidates &= ~v_bit;
            }
        };
    uint64_t all = n == 64 ? ~0ULL : (1ULL << n) - 1;
    expand(0, 0, all, 0);
    return res;
}

std::vector<uint64_t> masks(int n, const std::vector<std::pair<int, int>>& edges) {
    std::vector<uint64_t> m(n, 0);
    for (auto [u, w] : edges) { m[u] |= 1ULL << w; m[w] |= 1ULL << u; }
    return m;
}

std::vector<uint64_t> complement(int n, const std::vector<uint64_t>& m) {
    uint64_t full = (1ULL << n) - 1;
    std::vector<uint64_t> c(n);
    for (int v = 0; v < n; ++v) c[v] = full & ~m[v] & ~(1ULL << v);
    return c;
}

bool is_clique(const std::vector<uint64_t>& m, uint64_t mask) {
    for (uint64_t a = mask; a; a &= a - 1) {
        int u = std::countr_zero(a);
        if ((mask & ~(m[u] | (1ULL << u))) != 0) return false;
    }
    return true;
}

std::set<int> vertex_cover_2approx(int n, const std::vector<std::pair<int, int>>& edges) {
    std::vector<char> matched(n, 0);
    std::set<int> cover;
    for (auto [u, w] : edges)
        if (!matched[u] && !matched[w]) { matched[u] = matched[w] = 1; cover.insert(u); cover.insert(w); }
    return cover;
}

void check(bool ok, const std::string& msg) { if (!ok) throw std::runtime_error(msg); }

int main() {
    std::vector<std::pair<int, int>> e6 = {{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 4}, {2, 3}, {2, 4}, {3, 5}, {4, 5}};
    auto nb6 = masks(6, e6);
    auto r = bron_kerbosch(6, nb6);
    check(r.best_size == 3 && r.count == 5 && is_clique(nb6, r.best_mask), "g6");

    std::vector<std::pair<int, int>> ek;
    for (int u = 0; u < 9; ++u) for (int w = u + 1; w < 9; ++w) if (u / 3 != w / 3) ek.push_back({u, w});
    r = bron_kerbosch(9, masks(9, ek));
    check(r.best_size == 3 && r.count == 27, "K333");

    std::vector<std::pair<int, int>> ep;
    for (int i = 0; i < 5; ++i) {
        ep.push_back({i, (i + 1) % 5});
        ep.push_back({i, i + 5});
        ep.push_back({5 + i, 5 + (i + 2) % 5});
    }
    auto nbp = masks(10, ep);
    r = bron_kerbosch(10, nbp);
    check(r.best_size == 2 && r.count == 15, "petersen cliques");
    auto comp = complement(10, nbp);
    r = bron_kerbosch(10, comp);
    check(r.best_size == 4 && is_clique(comp, r.best_mask), "petersen alpha");
    int min_cover = 10 - r.best_size;
    auto cover = vertex_cover_2approx(10, ep);
    for (auto [u, w] : ep) check(cover.count(u) || cover.count(w), "is cover");
    check(min_cover <= static_cast<int>(cover.size()) && static_cast<int>(cover.size()) <= 2 * min_cover, "2-approx");
    std::cout << "cliques and covers: all tests passed\n";
}
// Bitmasks in 32-bit JS integers: n <= 31.
function popcount(x: number): number {
  let c = 0;
  while (x) { x &= x - 1; c++; }
  return c;
}

function ctz(x: number): number {
  return 31 - Math.clz32(x & -x);
}

function bronKerbosch(n: number, nb: number[]): { bestSize: number; bestMask: number; count: number } {
  let bestSize = 0, bestMask = 0, count = 0;
  const expand = (r: number, size: number, p: number, x: number): void => {
    if (p === 0 && x === 0) {
      count++;
      if (size > bestSize) { bestSize = size; bestMask = r; }
      return;
    }
    let pivot = -1, score = -1;
    for (let t = p | x; t; t &= t - 1) {
      const u = ctz(t), s = popcount(p & nb[u]);
      if (s > score) { score = s; pivot = u; }
    }
    let candidates = p & ~nb[pivot];
    while (candidates) {
      const vBit = candidates & -candidates, v = ctz(vBit);
      expand(r | vBit, size + 1, p & nb[v], x & nb[v]);
      p &= ~vBit;
      x |= vBit;
      candidates &= ~vBit;
    }
  };
  expand(0, 0, n === 31 ? 0x7fffffff : (1 << n) - 1, 0);
  return { bestSize, bestMask, count };
}

function masks(n: number, edges: [number, number][]): number[] {
  const m = new Array<number>(n).fill(0);
  for (const [u, w] of edges) { m[u] |= 1 << w; m[w] |= 1 << u; }
  return m;
}

function complement(n: number, m: number[]): number[] {
  const full = (1 << n) - 1;
  return m.map((x, v) => full & ~x & ~(1 << v));
}

function isClique(m: number[], mask: number): boolean {
  for (let a = mask; a; a &= a - 1) {
    const u = ctz(a);
    if ((mask & ~(m[u] | (1 << u))) !== 0) return false;
  }
  return true;
}

function vertexCover2Approx(n: number, edges: [number, number][]): Set<number> {
  const matched = new Array<boolean>(n).fill(false);
  const cover = new Set<number>();
  for (const [u, w] of edges)
    if (!matched[u] && !matched[w]) { matched[u] = matched[w] = true; cover.add(u); cover.add(w); }
  return cover;
}

function check(ok: boolean, msg: string): void { if (!ok) throw new Error(msg); }

const e6: [number, number][] = [[0, 1], [0, 2], [0, 3], [1, 2], [1, 4], [2, 3], [2, 4], [3, 5], [4, 5]];
const nb6 = masks(6, e6);
let r = bronKerbosch(6, nb6);
check(r.bestSize === 3 && r.count === 5 && isClique(nb6, r.bestMask), "g6");

const ek: [number, number][] = [];
for (let u = 0; u < 9; u++) for (let w = u + 1; w < 9; w++) if (Math.floor(u / 3) !== Math.floor(w / 3)) ek.push([u, w]);
r = bronKerbosch(9, masks(9, ek));
check(r.bestSize === 3 && r.count === 27, "K333");

const ep: [number, number][] = [];
for (let i = 0; i < 5; i++) ep.push([i, (i + 1) % 5], [i, i + 5], [5 + i, 5 + ((i + 2) % 5)]);
const nbp = masks(10, ep);
r = bronKerbosch(10, nbp);
check(r.bestSize === 2 && r.count === 15, "petersen cliques");
const comp = complement(10, nbp);
r = bronKerbosch(10, comp);
check(r.bestSize === 4 && isClique(comp, r.bestMask), "petersen alpha");
const minCover = 10 - r.bestSize;
const cover = vertexCover2Approx(10, ep);
for (const [u, w] of ep) check(cover.has(u) || cover.has(w), "is cover");
check(minCover <= cover.size && cover.size <= 2 * minCover, "2-approx");
console.log("cliques and covers: all tests passed");

Variant: maximum independent set by meet in the middle ()

Split the vertices into halves and of size about . For every subset , precompute , the largest independent set inside , with the recurrence for the lowest vertex of . Then enumerate independent subsets ; the vertices of still allowed are , and the best completion is . Both halves take steps.

def max_independent_set_mitm(n: int, edges: list[tuple[int, int]]) -> int:
    nb = [0] * n
    for u, w in edges:
        nb[u] |= 1 << w
        nb[w] |= 1 << u
    h = n // 2                      # A = vertices 0..h-1, B = vertices h..n-1
    nb_b = [nb[h + i] >> h for i in range(n - h)]   # neighbours inside B, re-indexed
    g = [0] * (1 << (n - h))
    for t in range(1, 1 << (n - h)):
        v = (t & -t).bit_length() - 1
        g[t] = max(g[t & ~(1 << v)], 1 + g[t & ~(1 << v) & ~nb_b[v]])
    best = 0
    # walk the independent subsets of A with the allowed-B mask carried along
    stack = [(0, 0, (1 << (n - h)) - 1, 0)]   # (next vertex, size, allowed B, chosen A mask)
    while stack:
        i, size, allowed, chosen = stack.pop()
        if i == h:
            best = max(best, size + g[allowed])
            continue
        stack.append((i + 1, size, allowed, chosen))          # skip vertex i
        if not (nb[i] & chosen):                               # take vertex i if independent
            stack.append((i + 1, size + 1, allowed & ~(nb[i] >> h), chosen | (1 << i)))
    return best


if __name__ == "__main__":
    ep = ([(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
          + [(5 + i, 5 + (i + 2) % 5) for i in range(5)])
    assert max_independent_set_mitm(10, ep) == 4                  # Petersen
    assert max_independent_set_mitm(7, [(i, (i + 1) % 7) for i in range(7)]) == 3  # C7
    assert max_independent_set_mitm(40, []) == 40
    path = [(i, i + 1) for i in range(39)]
    assert max_independent_set_mitm(40, path) == 20
    print("meet-in-the-middle MIS: ok")

Variant: greedy colouring in degeneracy order

import heapq


def degeneracy_order(adj: list[list[int]]) -> tuple[list[int], int]:
    """Repeatedly remove a minimum-degree vertex. Returns (colouring order, degeneracy)."""
    n = len(adj)
    deg = [len(a) for a in adj]
    removed = [False] * n
    heap = [(deg[v], v) for v in range(n)]
    heapq.heapify(heap)
    removal, k = [], 0
    while heap:
        d, v = heapq.heappop(heap)
        if removed[v] or d != deg[v]:
            continue                         # stale entry
        removed[v] = True
        removal.append(v)
        k = max(k, d)
        for w in adj[v]:
            if not removed[w]:
                deg[w] -= 1
                heapq.heappush(heap, (deg[w], w))
    return removal[::-1], k                  # colour in reverse removal order


def greedy(adj: list[list[int]], order: list[int]) -> list[int]:
    col = [-1] * len(adj)
    for v in order:
        used = {col[w] for w in adj[v]}
        c = 0
        while c in used:
            c += 1
        col[v] = c
    return col


if __name__ == "__main__":
    star = [[1, 2, 3, 4, 5]] + [[0] for _ in range(5)]     # Delta = 5, degeneracy 1
    order, k = degeneracy_order(star)
    col = greedy(star, order)
    assert k == 1 and max(col) + 1 == 2
    # a planar example: the octahedron (4-regular, planar, chromatic number 3)
    octa = [[1, 2, 3, 4], [0, 2, 4, 5], [0, 1, 3, 5], [0, 2, 4, 5], [0, 1, 3, 5], [1, 2, 3, 4]]
    order, k = degeneracy_order(octa)
    col = greedy(octa, order)
    assert k == 4 and max(col) + 1 <= k + 1
    assert all(col[u] != col[w] for u in range(6) for w in octa[u])
    print("degeneracy colouring: ok")

Real-world uses

  • Register allocation. A compiler computes, for each program point, which virtual registers (temporaries) are simultaneously live; two temporaries that are live at the same time interfere and cannot share a physical register. Colour the interference graph with colours, = number of machine registers. Chaitin and colleagues at IBM introduced this approach (Chaitin et al., "Register allocation via coloring", Computer Languages 6, 1981; Chaitin, "Register allocation and spilling via graph coloring", SIGPLAN Symposium on Compiler Construction, 1982). Its core is the simplify step: a node with fewer than neighbours can always be coloured last, so remove it, recurse, and put it back — exactly the degeneracy-order greedy colouring above. When every node has degree at least , pick one to spill to memory. Briggs, Cooper and Torczon's "optimistic colouring" (TOPLAS 1994) delays the spill decision because a high-degree node often still finds a free colour. GCC's IRA allocator descends from this line of work. Interference graphs of programs in strict SSA form are chordal (Hack, Grund and Goos, 2006; also Bouchez et al. and Brisk et al.), and chordal graphs can be coloured optimally in linear time, which is one reason SSA-based allocators are attractive. Many JITs instead use linear scan (Poletto and Sarkar, TOPLAS 1999), which is interval-graph colouring on approximate live ranges and trades a little code quality for speed; LLVM's default allocator is its own "greedy" allocator rather than classic graph colouring.
  • Timetabling and scheduling. Exams sharing a student conflict; colours are time slots. Meetings sharing a participant conflict; colours are rooms or slots. With interval conflicts (fixed start and end times) the greedy-by-start algorithm is optimal, which is why "minimum meeting rooms" is a heap problem and not an NP-hard one. See also the CPU scheduling page for the OS side of scheduling.
  • Frequency assignment. Transmitters that are close interfere and need different channels: colouring a geometric graph. Real formulations add separation constraints (channels must differ by at least 2), giving -labelling, but the colouring core is the same.
  • Parallel computation and sparse Jacobians. Two loop iterations that write the same memory location conflict; colouring the conflict graph gives batches that can run in parallel without locks. In scientific computing, grouping columns of a sparse Jacobian that share no row lets finite differences or automatic differentiation estimate many columns per evaluation: a colouring of the column-intersection graph (Curtis, Powell and Reid, 1974; surveyed by Gebremedhin, Manne and Pothen, "What color is your Jacobian?", SIAM Review, 2005).
  • Sudoku and puzzles. Sudoku is a 9-colouring of a fixed 81-vertex graph with some colours pre-assigned. The Module 5 capstone builds a constraint solver for it.
  • 2-SAT in practice. Map labelling where each feature has two candidate label positions (Formann and Wagner, 1991), two-sided placement problems in VLSI layout, and any configuration problem where each option is on or off and every rule names two options. Larger SAT solvers (MiniSat, CaDiCaL, Kissat) solve general CNF with conflict-driven clause learning; package managers use them for dependency resolution (see the next lesson), and they detect and exploit binary clauses with implication-graph techniques much like the one in this lesson.
  • Cliques and independent sets. Community and "dense core" detection in social and biological networks, finding groups of mutually compatible items, and coding theory (the largest code with a given minimum distance is a maximum independent set in a "too close" graph). Wireless scheduling picks a maximum-weight independent set of non-interfering links per time slot. Bron–Kerbosch is the standard enumeration routine in network-analysis libraries such as NetworkX (find_cliques).
  • Vertex cover and dominating set. Placing monitors on network links so that every link is watched is a vertex cover; placing servers, sensors or cameras so that every node is within one hop of one is a dominating set. On trees both are linear-time DPs (LeetCode's "Binary Tree Cameras" is exactly minimum dominating set on a tree).

Pitfalls & edge cases

  • The topological-order direction in 2-SAT. Kosaraju numbers components in topological order: true iff . Tarjan numbers them in reverse: true iff . Test against a brute-force checker on random formulas; a wrong direction passes many hand examples.
  • Literal indexing. Encoding as and as lets you negate with ^ 1. Mixing this with a " and " encoding in the same program is a classic bug. Pick one.
  • Forgetting one of the two edges per clause. The graph loses skew symmetry and the proof collapses. Every clause adds exactly two edges (one if both literals are the same).
  • Single-literal clauses. " must be true" is , edge . Do not try to special-case it by deleting vertices.
  • Recursion depth. At literals a recursive DFS overflows Python's stack and Java's default stack. Use iterative DFS, or raise limits and run in a thread with a large stack (Java), or use Kosaraju iteratively as above.
  • Treating "exactly one of three" as 2-SAT. It needs a 3-clause for the "at least one" half. If you find yourself needing it, the problem is either NP-hard or has extra structure you have not used.
  • Expecting greedy colouring to be optimal. It is optimal for interval graphs in start order, for chordal graphs in a perfect elimination order, and for bipartite graphs with BFS 2-colouring, but not in general. Report it as an upper bound.
  • Colour indices versus counts. Colours means colours; off-by-one in the "used" array size (it must have room for colour , i.e. size or ) causes out-of-bounds writes.
  • Overflow in inclusion–exclusion. overflows 64 bits for as small as 8. Reduce modulo a prime and accept a tiny one-sided error, or use big integers.
  • Bitmask width. 1 << n in Java/C++ int overflows at ; in JavaScript bit operators work on 32-bit signed integers. Use 64-bit (1L, 1ULL) or BigInt for wider sets.
  • Bron–Kerbosch without . Leaving out the excluded set reports non-maximal cliques and duplicates; leaving out pivoting is correct but exponentially slower on dense graphs.
  • Vertex cover on bipartite graphs. Do not use the 2-approximation; König's theorem gives the exact answer from a maximum matching.
  • Disconnected graphs. Chromatic number is the maximum over components; clique number likewise; independence number and vertex cover add up over components.

Variations

  • Horn-SAT (every clause has at most one positive literal) is also linear-time, by unit propagation; it is the logic behind Datalog evaluation and type inference.
  • MAX-2-SAT (satisfy as many 2-clauses as possible) is NP-hard, even though deciding whether all can be satisfied is linear. Counting satisfying assignments of a 2-CNF (#2-SAT) is #P-complete (Valiant, 1979).
  • XOR-SAT (every constraint is an XOR of any number of variables) is linear algebra over GF(2): Gaussian elimination, polynomial. Pairwise XOR constraints are the special case solved by parity union-find.
  • Edge colouring. Colour edges so that edges sharing an endpoint differ. Vizing's theorem: or colours always suffice, and bipartite graphs need exactly (König). Deciding which is NP-complete in general.
  • List colouring, precolouring extension, equitable colouring: generalizations used in scheduling with availability constraints.
  • Perfect graphs (bipartite, interval, chordal, comparability graphs): chromatic number equals clique number for every induced subgraph, and colouring is polynomial (via the ellipsoid method in general, combinatorially for the common subclasses).
  • Weighted independent set on trees, interval graphs and bounded-treewidth graphs is polynomial by DP; the treewidth technique (Module 6, DP on graphs and DAGs) generalizes the tree DP.
  • Exact cover and set cover are the set-system versions of independent set and dominating set; Knuth's Algorithm X with dancing links is the standard exact-cover search, and the greedy set cover achieves an approximation.

Planar graphs and the four-colour theorem

A graph is planar if it can be drawn in the plane with no crossing edges. Colouring the countries of a map so that neighbours differ is colouring the planar "adjacency" graph of the regions. Francis Guthrie conjectured in 1852 that four colours always suffice. Alfred Kempe published a proof in 1879 that stood for 11 years until Percy Heawood found the flaw in 1890; Heawood salvaged Kempe's argument to prove that five colours suffice (the five-colour theorem). Six colours is easy: Euler's formula gives for simple planar graphs with , so there is always a vertex of degree at most 5, and the degeneracy-order greedy colouring uses at most 6.

The four-colour theorem was proved by Kenneth Appel and Wolfgang Haken in 1976, the first major theorem whose proof depended essentially on a computer: they showed that every planar graph contains one of a large but finite set of "unavoidable" configurations (close to two thousand in their version), and verified by computer that each one is "reducible" (cannot appear in a minimal counterexample). Robertson, Sanders, Seymour and Thomas gave a simpler computer proof in 1997 with 633 configurations, together with a quadratic-time algorithm that actually finds a 4-colouring, and Georges Gonthier formally verified the theorem in the Coq proof assistant (announced 2005). Despite all that, deciding whether a planar graph is 3-colourable remains NP-complete (Garey, Johnson and Stockmeyer, 1976), even when every vertex has degree at most 4. So for planar graphs: 4 is always enough, 2 is BFS, and 3 is hard.

Practice ladder

Each problem is described in my own words; follow the link for the formal statement.

1. Is Graph Bipartite? (LeetCode 785) — Decide whether an undirected, possibly disconnected graph can be 2-coloured. Teaches 2-colouring as the base case of everything here.

Hint

BFS or DFS from every uncoloured vertex, alternating colours; a neighbour with the same colour means an odd cycle.

2. Flower Planting With No Adjacent (LeetCode 1042) — Gardens joined by paths, every garden on at most three paths, four flower types; give each garden a type different from its neighbours. Teaches the bound as an existence proof.

Hint

With and four colours, greedy in any order cannot get stuck.

Solution
def garden_no_adj(n: int, paths: list[list[int]]) -> list[int]:
    adj: list[list[int]] = [[] for _ in range(n)]
    for x, y in paths:
        adj[x - 1].append(y - 1)
        adj[y - 1].append(x - 1)
    res = [0] * n
    for v in range(n):
        used = {res[w] for w in adj[v]}
        res[v] = next(c for c in (1, 2, 3, 4) if c not in used)
    return res


got = garden_no_adj(4, [[1, 2], [2, 3], [3, 4], [4, 1], [1, 3], [2, 4]])
assert all(got[a - 1] != got[b - 1] for a, b in [[1, 2], [2, 3], [3, 4], [4, 1], [1, 3], [2, 4]])
assert sorted(got) == [1, 2, 3, 4]          # K4 needs all four types
assert garden_no_adj(3, [[1, 2], [2, 3]]) == [1, 2, 1]

time. The proof of correctness is the one-line argument.

3. Possible Bipartition (LeetCode 886) — Split people into two groups given pairs who refuse to share a group. Teaches modelling "dislikes" as edges and splitting as 2-colouring.

Hint

Same as problem 1 after building the graph. Alternatively, union-find with "enemy of my enemy" representatives.

4. Building Teams (CSES 1668) — Assign pupils to two teams so that friends are on different teams, printing the assignment. Teaches outputting the colouring, iteratively, at scale.

Hint

Iterative BFS to avoid recursion limits; print "IMPOSSIBLE" on an odd cycle.

5. Divide Intervals Into Minimum Number of Groups (LeetCode 2406) — Partition closed intervals into the fewest groups with no overlap inside a group. Teaches interval-graph colouring and why greedy is optimal there.

Hint

Sort by start; a min-heap holds the end time of the last interval in each group. Reuse the group whose last end is smallest if it ends strictly before the new start.

Solution
import heapq


def min_groups(intervals: list[list[int]]) -> int:
    ends: list[int] = []                       # end of the latest interval in each group
    for start, end in sorted(intervals):
        if ends and ends[0] < start:           # closed intervals: touching endpoints overlap
            heapq.heapreplace(ends, end)
        else:
            heapq.heappush(ends, end)
    return len(ends)


assert min_groups([[5, 10], [6, 8], [1, 5], [2, 3], [1, 10]]) == 3
assert min_groups([[1, 3], [5, 6], [8, 10], [11, 13]]) == 1
assert min_groups([[1, 2], [2, 3]]) == 2

. The heap size at the end equals the maximum number of intervals covering one point, the clique number, which the correctness section showed is optimal.

6. Satisfiability of Equality Equations (LeetCode 990) — Variables with "equal" and "not equal" constraints over an unlimited domain. Teaches when you do not need 2-SAT: with unlimited values, union-find on equalities, then check inequalities.

Hint

Union all == pairs first, then reject any != pair in the same set. Order matters: process all equalities before any inequality.

7. Binary Tree Cameras (LeetCode 968) — Place the fewest cameras on tree nodes so that every node is watched by itself, its parent or a child. Teaches that minimum dominating set, NP-hard in general, is a linear DP on trees.

Hint

Post-order with three states per node: has a camera, covered without a camera, not covered. A leaf's parent must take the camera; greedy from the leaves up is optimal.

8. Giant Pizza (CSES 1684) — Each of up to people gives two topping wishes (include or exclude); choose toppings so every person gets at least one wish. Teaches the canonical 2-SAT encoding and output.

Hint

One variable per topping, one clause per person. Build the implication graph, run iterative SCC, output +/- per topping or IMPOSSIBLE.

Solution
def giant_pizza(m: int, wishes: list[tuple[str, int, str, int]]) -> str:
    adj: list[list[int]] = [[] for _ in range(2 * m)]

    def lit(sign: str, t: int) -> int:
        return 2 * (t - 1) + (0 if sign == "+" else 1)

    for s1, t1, s2, t2 in wishes:
        a, b = lit(s1, t1), lit(s2, t2)
        adj[a ^ 1].append(b)
        adj[b ^ 1].append(a)
    size = 2 * m
    order, seen = [], [False] * size
    for s in range(size):
        if seen[s]:
            continue
        seen[s] = True
        stack = [(s, 0)]
        while stack:
            u, i = stack[-1]
            if i < len(adj[u]):
                stack[-1] = (u, i + 1)
                if not seen[adj[u][i]]:
                    seen[adj[u][i]] = True
                    stack.append((adj[u][i], 0))
            else:
                stack.pop()
                order.append(u)
    radj: list[list[int]] = [[] for _ in range(size)]
    for u in range(size):
        for w in adj[u]:
            radj[w].append(u)
    comp, c = [-1] * size, 0
    for s in reversed(order):
        if comp[s] == -1:
            comp[s], st = c, [s]
            while st:
                u = st.pop()
                for w in radj[u]:
                    if comp[w] == -1:
                        comp[w] = c
                        st.append(w)
            c += 1
    out = []
    for v in range(m):
        if comp[2 * v] == comp[2 * v + 1]:
            return "IMPOSSIBLE"
        out.append("+" if comp[2 * v] > comp[2 * v + 1] else "-")
    return " ".join(out)


def ok(ans: str, wishes: list[tuple[str, int, str, int]]) -> bool:
    signs = ans.split()
    return all(signs[t1 - 1] == s1 or signs[t2 - 1] == s2 for s1, t1, s2, t2 in wishes)


w1 = [("+", 1, "+", 2), ("-", 1, "+", 3), ("+", 4, "-", 2), ("-", 3, "-", 4)]
assert ok(giant_pizza(4, w1), w1)
w2 = [("+", 1, "+", 1), ("-", 1, "-", 1)]       # wants topping 1 and wants it absent
assert giant_pizza(1, w2) == "IMPOSSIBLE"

for people and toppings.

9. Ring Road 2 (Codeforces 27D) — Cities on a circle and new roads between pairs; each road goes inside or outside the ring and roads on the same side must not cross. Teaches spotting the binary choice and the pairwise "must differ" rule.

Hint

Two chords and cross iff exactly one of lies strictly between and (after normalizing ). Add for each crossing pair; 2-SAT or bipartite check.

10. The Door Problem (Codeforces 776D) — Doors are initially locked or unlocked, each door is wired to exactly two switches, and flipping a switch toggles all its doors. Can all doors be unlocked at once? Teaches XOR constraints.

Hint

Door with switches and initial state : you need . Either 2-SAT with XOR/equality clauses or union-find with parity.

11. The Road to Berland is Paved With Good Intentions (Codeforces 228E) — Roads are asphalted or not; choosing a city toggles all its roads; make every road asphalted. Teaches that each city is chosen at most once (twice cancels), which makes it a boolean variable.

Hint

Road with state needs . Output the set of true variables.

12. Close Group (AtCoder ABC 187 F) — Remove edges from a graph on at most 18 vertices so every connected component becomes a complete graph, minimizing the number of components. Teaches clique cover = chromatic number of the complement, solved by subset DP.

Hint

Precompute which vertex subsets are cliques, then over clique submasks containing the lowest vertex of . is fine in C++; in Python use the inclusion–exclusion variant on the complement.

Solution
def close_group(n: int, edges: list[tuple[int, int]]) -> int:
    nb = [0] * n
    for a, b in edges:
        nb[a - 1] |= 1 << (b - 1)
        nb[b - 1] |= 1 << (a - 1)
    full = 1 << n
    clique = [False] * full
    clique[0] = True
    for s in range(1, full):
        v = (s & -s).bit_length() - 1
        rest = s & ~(1 << v)
        clique[s] = clique[rest] and (rest & ~nb[v]) == 0
    f = [0] * full
    for s in range(1, full):
        low, best, t = s & -s, n, s
        while t:
            if t & low and clique[t]:
                best = min(best, f[s ^ t] + 1)
            t = (t - 1) & s
        f[s] = best
    return f[full - 1]


assert close_group(3, [(1, 2)]) == 2
assert close_group(4, [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]) == 1
assert close_group(10, []) == 10
assert close_group(4, [(1, 2), (2, 3), (3, 4)]) == 2   # path: {1,2}, {3,4}

time, memory.

13. Helping Hiasat (Codeforces 1105E) — A log of "change handle" events and "friend visits" events, with at most 40 friends; a friend is happy if every visit of theirs saw their name. Maximize happy friends. Teaches reducing to maximum independent set with and solving by meet in the middle or Bron–Kerbosch.

Hint

Split the log into segments between handle changes. Two friends who both visit within the same segment conflict (only one name can be shown). The answer is a maximum independent set of the conflict graph.

Solution
def helping_hiasat(events: list[tuple[int, str]]) -> int:
    ids: dict[str, int] = {}
    segments: list[set[int]] = []
    for typ, *rest in events:
        if typ == 1:
            segments.append(set())
        else:
            name = rest[0]
            ids.setdefault(name, len(ids))
            segments[-1].add(ids[name])
    n = len(ids)
    nb = [0] * n
    for seg in segments:
        mask = sum(1 << v for v in seg)
        for v in seg:
            nb[v] |= mask & ~(1 << v)
    h = n // 2
    g = [0] * (1 << (n - h))
    nb_b = [nb[h + i] >> h for i in range(n - h)]
    for t in range(1, 1 << (n - h)):
        v = (t & -t).bit_length() - 1
        rest = t & ~(1 << v)
        g[t] = max(g[rest], 1 + g[rest & ~nb_b[v]])
    best = 0
    stack = [(0, 0, (1 << (n - h)) - 1, 0)]
    while stack:
        i, size, allowed, chosen = stack.pop()
        if i == h:
            best = max(best, size + g[allowed])
            continue
        stack.append((i + 1, size, allowed, chosen))
        if not nb[i] & chosen:
            stack.append((i + 1, size + 1, allowed & ~(nb[i] >> h), chosen | (1 << i)))
    return best


log = [(1,), (2, "motarack"), (2, "mike"), (1,), (2, "light")]
assert helping_hiasat(log) == 2
log2 = [(1,), (2, "alice"), (2, "bob"), (2, "tanyaromanova")]
assert helping_hiasat(log2) == 1

with friends, plus linear work over the log.

Common mistakes & interview follow-ups

  • "Why can't you just propagate greedily from any variable?" You can, with the Even–Itai–Shamir fix-and-propagate rule, in . The SCC method is the linear version. Being able to state both shows you understand why 2-SAT is easy.
  • "What if each item has three choices?" Then it is 3-colouring or 3-SAT territory: NP-complete. Ask for constraints on (subset DP, backtracking) or for structure (tree, interval, bipartite, bounded treewidth).
  • "Find all solutions / count solutions." Counting 2-SAT solutions is #P-complete; enumerating them can be done with polynomial delay by branching on a variable and re-checking satisfiability, but the number of solutions itself can be exponential.
  • "Find the lexicographically smallest satisfying assignment." Fix variables in order: try false, check satisfiability (with the forced literal as a unit clause), keep it if satisfiable. ; faster incremental methods exist.
  • "Is greedy colouring with largest-degree-first optimal?" No. Give the crown graph or a small counterexample; say what guarantee it does have (, or degeneracy in smallest-last order).
  • "Minimum meeting rooms is colouring, so isn't it NP-hard?" Not on interval graphs. State the clique argument for greedy optimality.
  • "How would you colour a graph with vertices?" DSATUR or smallest-last greedy, then local search (tabu search such as TabuCol, or Kempe-chain swaps) if you need fewer colours. No exact method scales.
  • "Maximum clique on 50 vertices?" Bron–Kerbosch with pivoting and bitsets, plus a colouring-based upper bound for branch and bound (Tomita's MCS family). For , meet in the middle on independent sets of the complement is predictable.
  • "Vertex cover approximation: can you do better than 2?" Not by much in general: getting below is NP-hard (Khot, Minzer and Safra, 2017), and below 2 is hard under the Unique Games Conjecture (Khot and Regev, 2008). For bipartite graphs it is exact via matching, and for small covers there are fixed-parameter algorithms with running time like .

Quick quiz

1. Write (exactly one of ) as 2-SAT clauses, and list the four implication edges they create.

Answer

. Edges: , from the first; , from the second.

2. Using Tarjan's SCC algorithm, component ids come out with sinks first. Which comparison decides that is true?

Answer

: 's component is closer to the sinks, which means later in topological order.

3. A graph has maximum degree 7 and is neither complete nor an odd cycle. What is the best upper bound you can state on its chromatic number, and which result gives it?

Answer

7, by Brooks' theorem (for a connected graph; apply per component). Greedy alone guarantees only 8.

4. For , roughly how many operations do the subset DP and the inclusion–exclusion algorithm take?

Answer

versus .

5. Why does taking both endpoints of a maximal matching give a vertex cover of at most twice the optimum?

Answer

Any uncovered edge could be added to the matching, contradicting maximality, so it is a cover. Matched edges are disjoint, so any cover contains at least one distinct endpoint per matched edge: , and the output has vertices.

Further reading / sources

  • Bengt Aspvall, Michael F. Plass, Robert E. Tarjan, "A linear-time algorithm for testing the truth of certain quantified boolean formulas", Information Processing Letters 8(3), 1979 — the implication-graph algorithm.
  • Melven R. Krom, "The decision problem for a class of first-order formulas in which all disjunctions are binary", Zeitschrift für mathematische Logik und Grundlagen der Mathematik 13, 1967; Shimon Even, Alon Itai, Adi Shamir, "On the complexity of timetable and multicommodity flow problems", SIAM Journal on Computing 5(4), 1976.
  • cp-algorithms: 2-SAT and Strongly connected components.
  • Daniel Brélaz, "New methods to color the vertices of a graph", Communications of the ACM 22(4), 1979 (DSATUR); D. J. A. Welsh and M. B. Powell, "An upper bound for the chromatic number of a graph and its application to timetabling problems", The Computer Journal 10(1), 1967.
  • Andreas Björklund, Thore Husfeldt, Mikko Koivisto, "Set partitioning via inclusion–exclusion", SIAM Journal on Computing 39(2), 2009.
  • Coen Bron and Joep Kerbosch, "Algorithm 457: finding all cliques of an undirected graph", Communications of the ACM 16(9), 1973; Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi, "The worst-case time complexity for generating all maximal cliques and computational experiments", Theoretical Computer Science 363(1), 2006.
  • G. J. Chaitin, "Register allocation and spilling via graph coloring", SIGPLAN Notices 17(6), 1982; Preston Briggs, Keith D. Cooper, Linda Torczon, "Improvements to graph coloring register allocation", ACM TOPLAS 16(3), 1994; Keith Cooper and Linda Torczon, Engineering a Compiler, chapter 13 "Register Allocation".
  • Kenneth Appel and Wolfgang Haken, "Every planar map is four colorable", Illinois Journal of Mathematics 21, 1977; Neil Robertson, Daniel Sanders, Paul Seymour, Robin Thomas, "The four-colour theorem", Journal of Combinatorial Theory, Series B 70, 1997; Robin Wilson, Four Colors Suffice, Princeton University Press, 2002 (the history).
  • CLRS, 4th ed., chapter 34 "NP-Completeness" (3-SAT, clique, vertex cover reductions) and chapter 35 "Approximation Algorithms" (35.1, the vertex-cover 2-approximation); Steven Skiena, The Algorithm Design Manual, 3rd ed., sections 19.7 "Vertex Coloring", 19.1 "Clique", 19.2 "Independent Set", 19.3 "Vertex Cover".
  • Antti Laaksonen, Competitive Programmer's Handbook, chapter 17 "Strong connectivity" (2-SAT section).

Previous lesson: Network Flow · Next lesson: Graph Algorithms in the Real World

Related: Module 4 overview · Connectivity: SCCs & Condensation · DFS · Bipartite Matching · Intervals · Greedy Algorithms · Bit Manipulation · Recursion & Backtracking · Course home