Graph Theory37 sections · 1633 units
Open in Course

Tracking Component Sizes

Application 3

Sometimes you want to track: "What is the size of the largest component?" Since you already maintain a size array for union by size, tracking this is easy.

After each union, check if the new component size exceeds your current maximum. Keep a global maxSize variable.

if union(u, v) succeeded then
    maxSize := max(maxSize, size[find(u)])

This pattern appears in problems asking about the largest connected component or when sizes affect the answer.