Largest group of mutual strangers in an acquaintance forest

A group of mutual strangers is a set of people where no two know each other.
In graph terms, people are vertices, "knows" is an edge, and the task asks
for a maximum independent set. On a general graph that problem is
NP-hard, so the stated condition carries the whole question: the
acquaintances contain no cycle, so the graph is a forest (each friend
group is a tree). On a tree, maximum independent set is a clean dynamic
program.

Brute force. Try every subset of people, keep the ones with no
internal edge, and take the largest. That is O(2^n · m). Say it in one
sentence and move on. It is only the baseline, and it is also the honest
answer for a general graph (see follow-ups).

Greedy that works on trees. A leaf can always be in an optimal group:
if an optimal group uses the leaf's only neighbor instead, swap that
neighbor for the leaf and the group stays valid and the same size. So you
can repeatedly take a leaf, drop its neighbor, and repeat. That gives a
correct O(n + m) answer. Mention it, because a strong candidate spots the
exchange argument. The DP below is easier to extend to weights and to
rebuilding the group, so it is what we code.

Tree DP (optimal). Root each tree anywhere. For every person v
compute two numbers over v's subtree:

• take[v] = largest group that includes v = 1 + sum(skip[c]) over
  children c (a child cannot join if v is in).
• skip[v] = largest group that excludes v =
  sum(max(take[c], skip[c])) (each child is free to join or not).

The answer for a tree is max(take[root], skip[root]), and the answer for
the forest is the sum over trees, because separate trees never constrain
each other. People with no acquaintances are one-node trees and always join.

To return the group itself, walk top-down: include a person when the parent
is excluded and take >= skip, otherwise exclude them.

Invariants:

• Children are processed before their parent (reverse BFS order), so both
  values of every child are final when the parent reads them.
• A chosen person never has a chosen parent, so no edge lies inside the group.

Input validation matters here because the whole method depends on the
forest condition. Union-find over the edges detects a cycle (or a
duplicate pair, or someone listed as knowing themselves) in near-linear time,
and the function rejects such input instead of returning a wrong number.
The code is iterative, so a chain of 100,000 people does not hit Python's
recursion limit.

from collections import deque


def largest_stranger_group(n: int, connections: list[list[int]]) -> list[int]:
    """Return a largest set of people (sorted) in which no two know each other.

    Requires the acquaintance graph to be a forest (no cycles, no repeated pairs).
    """
    parent_uf = list(range(n))

    def find(x: int) -> int:
        while parent_uf[x] != x:
            parent_uf[x] = parent_uf[parent_uf[x]]
            x = parent_uf[x]
        return x

    adj: list[list[int]] = [[] for _ in range(n)]
    for a, b in connections:
        if not (0 <= a < n and 0 <= b < n) or a == b:
            raise ValueError(f"invalid pair {a}, {b}")
        ra, rb = find(a), find(b)
        if ra == rb:
            raise ValueError("acquaintances contain a cycle; not a forest")
        parent_uf[ra] = rb
        adj[a].append(b)
        adj[b].append(a)

    parent = [-1] * n
    seen = [False] * n
    order: list[int] = []          # BFS order: every parent before its children
    roots: list[int] = []
    for start in range(n):
        if seen[start]:
            continue
        seen[start] = True
        roots.append(start)
        queue = deque([start])
        while queue:
            v = queue.popleft()
            order.append(v)
            for w in adj[v]:
                if not seen[w]:
                    seen[w] = True
                    parent[w] = v
                    queue.append(w)

    take = [1] * n                 # best group in v's subtree that includes v
    skip = [0] * n                 # best group in v's subtree that excludes v
    for v in reversed(order):      # children before parents
        p = parent[v]
        if p != -1:
            take[p] += skip[v]
            skip[p] += max(take[v], skip[v])

    chosen = [False] * n
    for v in order:                # parents before children
        p = parent[v]
        if p != -1 and chosen[p]:
            continue               # parent is in, so v must stay out
        chosen[v] = take[v] >= skip[v]

    return [v for v in range(n) if chosen[v]]


def largest_stranger_group_size(n: int, connections: list[list[int]]) -> int:
    return len(largest_stranger_group(n, connections))

• Validation with union-find: O(m · α(n)) time, O(n) space.
• Building adjacency, BFS, DP, and reconstruction: O(n + m) time, O(n + m)
  space. In a forest m ≤ n − 1, so everything is O(n).

• n = 0, connections = [] → [] (size 0).
• n = 1, connections = [] → [0].
• n = 4, connections = [] → [0, 1, 2, 3] (nobody knows anybody).
• n = 2, connections = [[0, 1]] → size 1 ([0] or [1]).
• Path 0-1-2-3-4: connections = [[0,1],[1,2],[2,3],[3,4]] → [0, 2, 4].
• Star with center 0 and 5 leaves: n = 6, [[0,1],[0,2],[0,3],[0,4],[0,5]]
  → [1, 2, 3, 4, 5] (greedy "take the hub" fails here).
• Two trees plus an isolated person: n = 6, [[0,1],[1,2],[3,4]] → size 4,
  e.g. [0, 2, 3, 5].
• Tree where the root is skipped but grandchildren matter:
  n = 7, [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]] → [0, 3, 4, 5, 6] (size 5).
• Cycle [[0,1],[1,2],[2,0]] → raises ValueError.
• Duplicate pair [[0,1],[1,0]] → raises ValueError (it closes a 2-cycle).
• Chain of 100,000 people → size 50,000, no recursion error.

1. Each person knows at most two others (paths and cycles). Components
   are paths or simple cycles. A path of k people allows ceil(k / 2), a
   cycle of k allows floor(k / 2). Or run the tree DP twice on a cycle: once
   with one chosen vertex forced out, once forced in.
2. Weighted people (each has an influence score; maximize the total).
   Replace 1 + with w[v] + in take. The leaf greedy no longer works,
   which is why the DP is the better base.
3. General graph, small n (n ≤ 40). NP-hard in general. Use branch
   and bound: pick the highest-degree vertex v; either drop v, or take
   v and drop its neighbors; vertices of degree ≤ 1 are taken greedily.
   Or meet in the middle over two halves with bitmasks (O(2^(n/2) · n)).
   Equivalently, find the maximum clique in the complement graph.
4. Two teams, everyone knows only people on the other team (bipartite).
   By König's theorem, max independent set = n − maximum matching. Use
   Hopcroft–Karp for O(m·√n), and recover the set from the minimum vertex
   cover.
5. Acquaintances arrive one at a time; report the answer after each.
   For a forest, adding an edge between two trees changes only the merged
   tree. Recompute that tree's DP, or keep a rerooting DP for O(depth)
   updates. Link-cut trees are a staff-level aside.

Mid-level (L4)

• Recognizes "no two know each other" as an independent set and builds an
  adjacency list.
• Writes the take/skip DP correctly on one tree, possibly recursively.
• Handles isolated people and multiple components when prompted.

Senior (L5)

• Asks what the structural condition is and explains why it matters
  (general graph is NP-hard, a forest is linear).
• Iterative traversal so deep chains are safe; returns the actual group, not
  just the size.
• Validates the input (cycle, self-pair, out-of-range id) and tests stars,
  paths, and forests.
• Handles the weighted follow-up and the degree ≤ 2 variant quickly.

Staff (L6+)

• Gives the leaf exchange argument and knows why it breaks with weights.
• Places the problem precisely: König for bipartite graphs, branch and
  bound or meet in the middle for small general graphs, approximation
  limits otherwise.
• Discusses the incremental version and what state to keep per component.