PROBLEM LINKS
DIFFICULTY
MEDIUM
Solution: Tree traversal, DFS
Complexity: O(N)
EXPLANATION
Consider a complete binary tree T with 2^d-1 nodes, where d is the maximum depth of any of the given maps. Each city in this binary tree has a unique path from the root of T (and therefore a unique control string). For a given map, every city has a unique control string. Now each city on the map can uniquely be mapped to a city on T by following its control string on T.
To solve the problem, at each city in T, store a variable count, which denotes the number of maps which has a valid control string from root to the present city in T. Initially, all counts are 0. On adding a map, we can update the count of a city in T, by doing a depth first search (or any other traversal) on the given map and also computing the corresponding city number in T. Note that the length of the control string of any city is equal to the level of the city, assuming that root is at level-0.
Now we can just splice all the maps into T, renaming the cities in the map whenever necessary and find the required answer by looking at the count and level of each node in T. Since the total number of cities are 100 * 1000, we only need to consider atmost 100000 nodes in T as the rest of the cities in T will never correspond to a valid control string.