Uber Zone Clusters

Problem Preview

"Uber optimizes its driver dispatch system by analyzing the connectivity between different zones in a city. There are n zones, and each zone is assigned a specific traffic signature based on its road infrastructure. Two zones are considered part of the same cluster if the greatest common divisor (GCD) of their traffic signatures is greater than 1. Connectivity is transitive: if zone A is connected to zone B, and zone B is connected to zone C, all three zones are part of the same cluster. Given an array of n integers representing the traffic signatures of the zones, determine the size of the cluster to which each zone belongs. Example: It is given that n = 3, signature = [1, 2, 4]. Based on the given transitive properties, zones at indices 1 and 2 are connected (O-based indexing). The zone at vertex 0 is not connected to any other zone, so the cluster containing it has a size of 1. The zone at vertex 1 is connected to the zone at vertex 2, and 2 is connected only to 1, forming a cluster of size 2. Hence, the answer returned is [1, 2, 2]."