Graph Theory37 sections · 1633 units
Open in Course

Pattern - Indirect Grouping

Mapping Data

Sometimes nodes are not numbers 1n1 \ldots n. They might be strings, emails, or coordinates. You need to map these complex objects to integer IDs before using DSU. Use a hash map: when you see a new object, assign it the next available ID.

Then proceed with standard DSU on the IDs. This pattern appears whenever the "nodes" are not naturally numbered. The mapping itself takes O(1)O(1) amortized per lookup with a hash map, so it does not change the overall time complexity.