1221. The Largest Group With No Two in Conflict

There are n items numbered 1 to n and m conflicting pairs. Choose as many items as possible with no conflicting pair among them. Report how many you chose and which, as the lexicographically smallest such choice written in increasing order.

5 items, conflicts 1-2, 2-3, 3-4, 4-5 3 1 3 5

## What most people try first

Every subset, all 2^n of them, keeping the largest conflict-free one. At n = 20 that is a million subsets, each costing O(m) to check.

Greedy is the other instinct and it is badly wrong here. Taking items in order while they stay conflict-free gives 1 3 5 on the example, which is optimal, and on the conflicts 1-2, 1-3, 1-4, 1-5 it takes item 1 and then nothing, reporting 1 where 2 3 4 5 gives 4. One item can block many.

## The method

Walk the items in order and at each one decide TAKE or SKIP:

go(i, chosen): if the current choice beats the best, record it if i == n: return if size of current choice + (n - i) <= best size: return if item i conflicts with nothing already chosen: take it; go(i + 1, chosen + i); put it back go(i + 1, chosen)

## The counting bound

The items from i onward number n - i, so the largest the current branch can ever reach is the size of the current choice plus n - i. If that is at most the best size already found, the branch cannot improve and is dead.

## What makes a bound sound

A bound is sound when every branch it skips contains no answer better than the one already found. That is the only thing that has to be proved, and it has to be proved rather than felt: a bound that is nearly sound gives a plausible wrong answer, which is the most expensive kind.

The shape of the argument is always the same. Find a quantity that moves in one direction as the search descends, then show that its value at the current node already rules the branch out. If the quantity can move both ways, the bound is not sound however reasonable it looks.

Here the quantity is the current size plus the items remaining, which never increases as the search descends: taking an item adds one to the size and removes one from the remaining, leaving it unchanged, and skipping an item leaves the size alone and removes one from the remaining, decreasing it. A quantity that never increases and is already too small to beat the incumbent cannot recover, which is exactly the argument the bound needs.

## Why trying TAKE before SKIP gives the lexicographically smallest

Two choices of the same size differ at some first item, which one of them takes and the other does not. The one that takes it is lexicographically smaller when both are written in increasing order, because the list that contains the smaller number earlier is smaller. So among choices of equal size, the search reaches the lexicographically smallest one FIRST if at every item it tries taking before skipping. Recording a new best only on a STRICT improvement then keeps that first one, which is why the comparison is > and not >=.

Getting that comparison wrong does not change the reported size. It changes which choice is printed, to the last one found rather than the first, and that is the whole second line of the answer.

## The settled boundaries

With no conflicts every item fits, so the answer is n and the list is 1 2 ... n. With every pair in conflict only one item fits and the smallest such choice is item 1. The answer is never empty, since a single item conflicts with nothing on its own. Both extremes are tested, as are a path, a cycle and a set of disjoint pairs.

## Cost

Worst case O(2^n), which is unavoidable: this is maximum independent set, which is NP-hard. The bound removes whole depths once a good choice is found early, and trying TAKE first helps there too, since it finds a large choice quickly.

The size is at most 20 and the bitmask of chosen items therefore fits in 20 bits, well inside the 32 that a bitwise operator keeps.

Constraints - `1 ≤ n ≤ 20` - `0 ≤ m ≤ n * (n - 1) / 2` - `1 ≤ u, v ≤ n` and `u != v` - no pair is repeated