Largest group of mutual strangers in an acquaintance forest

You are given n people numbered 0 to n - 1 and a list connections, where each pair [a, b] means a and b know each other (the relation is symmetric).

The acquaintances contain no cycle: you can never start at a person, follow a chain of distinct acquaintances, and come back to the start. So every friend group is a tree, and some people may know nobody.

Implement:

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

Return a largest possible group of people in which no two members know each other, as a sorted list. If several groups tie, return any of them. Raise an error if the input breaks the rules (a cycle, a repeated pair, a person paired with themselves, or an id out of range).

Constraints

• 0 <= n <= 10^5
• 0 <= len(connections) <= n - 1
• Aim for linear time. Chains can be as long as n, so avoid deep recursion.

Example 1

n = 6
connections = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5]]
output: [1, 2, 3, 4, 5]

Person 0 knows everyone else. Leaving 0 out lets the other five form a group of strangers.

Example 2

n = 7
connections = [[0, 1], [1, 2], [3, 4], [4, 5]]
output: [0, 2, 3, 5, 6]   (size 5)

Two chains of three people each give two strangers (the ends), and person 6 knows nobody, so they always join.

Reconstructed from the reported question; details may differ from what interviewers ask.