Graph Coloring

What is this?

"Colouring" here means the plain version: give every node a component id, then answer questions about the components rather than about the nodes. Minimize Malware Spread is the archetype — a network, a set of initially infected nodes, and the question of which single one to disinfect. The graph work is a routine flood fill. The reasoning after it is what the problem is for.

💡 Fun fact: the trap in Minimize Malware Spread is that removing an infected node usually accomplishes nothing. If its component holds another infected node, the malware reaches every node there anyway and the final count is unchanged. Only a component with exactly one infected node can be saved — which means the answer is decided by a filter most people never apply, and a solution that simulates the spread once per candidate is not just slower, it is easy to get wrong on the tie-break.

🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.

The one-line idea: colour the components, then count. A node is only worth removing if it is the sole infection in its component, and among those the best is the one guarding the most nodes.

1. Colour, then count

colour = [-1] * n
for start in range(n):
    if colour[start] == -1:
        stack = [start]
        while stack:
            u = stack.pop()
            if colour[u] != -1: continue
            colour[u] = start                        # the first node found is the id
            stack += [v for v in range(n) if graph[u][v] and colour[v] == -1]

size = Counter(colour)                               # nodes per component
infected = Counter(colour[u] for u in initial)       # infected per component

Two counters and the rest is arithmetic. The adjacency matrix makes the traversal O(n²), which is fine at n ≤ 300 and worth naming out loud — with an adjacency list it would be O(n + e).

2. The decision

best, best_saved = min(initial), 0
for u in sorted(initial):                            # ascending → ties resolve themselves
    if infected[colour[u]] == 1 and size[colour[u]] > best_saved:
        best, best_saved = u, size[colour[u]]
return best

Two details carry the whole answer. The == 1 filter is the insight: a component with two or more infected nodes is doomed regardless. Ascending iteration with a strict > implements "smallest index on a tie" without a special case — and the initial min(initial) covers the case where no component qualifies, where every removal is equally useless and the smallest index wins by default.

3. A 30-second worked example

graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1, 2]

colouring:  all three nodes are mutually connected → one component {0,1,2}
size:       {c: 3}
infected:   {c: 2}      ← two infected nodes in the same component

candidate 1: infected[c] == 2, not 1  → skip
candidate 2: infected[c] == 2, not 1  → skip

nothing qualifies → fall back to min(initial) = 1

Removing node 1 leaves node 2 to infect everything; removing node 2 leaves node 1 to do the same. Both end with all three infected, so the answer is decided purely by the tie-break — which is why the fallback is not an edge case to bolt on afterwards but part of the specification.

4. Where you'll actually meet this

• Epidemic and outbreak modelling. Which single quarantine reduces the eventual case count is this question, unchanged.
• Network security. Isolating a compromised host only helps if it is the only compromise in its segment.
• Rumour and misinformation containment. Removing one source matters only when it is the sole source in its cluster.
• Failure-domain analysis. Component size is blast radius, and the counting argument is the same.
• Vaccination strategy. Prioritising by component size is a coarse but real version of targeted immunisation.

5. Problems in this chapter

▶ Minimize Malware Spread

Remove one initially infected node to minimise the final infected count. Colour the components, keep only those with exactly one infection, and pick the largest.
Pattern: component colouring + counting argument. Target: O(n²) on an adjacency matrix, O(n) space.

6. Common pitfalls 🚫

• Removing any infected node and hoping. Only a component with exactly one infection can be saved.
• Simulating the spread once per candidate. Correct but O(n³), and it still needs the tie-break handled explicitly.
• Forgetting the fallback. When no component qualifies the answer is the smallest index in initial, not -1 and not nothing.
• Getting the tie-break backwards. Iterate ascending and use a strict >; the first best index then wins for free.
• Confusing size with saved count. What you save is the whole component, not the number of infections in it.
• Assuming the removed node stays clean. It is only removed from the initial set; it can still be infected by neighbours.
• Reading the diagonal as edges. graph[i][i] is 1 by definition and is not a real connection.

7. Key takeaways

1. Colour the components first, then treat the question as counting.
2. Exactly one infection per component is the filter the whole problem turns on.
3. The saving is the component's size, not the number of infections in it.
4. Ascending iteration plus a strict comparison implements the tie-break with no extra code.
5. Handle "nothing qualifies" as part of the spec — it is a common input, not an afterthought.
6. Name the representation's cost. O(n²) here comes from the matrix, not from the algorithm.
7. Why interviewers like it: the traversal is trivial, so all the signal is in whether you reason about what a removal actually changes.

Order: Minimize Malware Spread.