The problem statement is "If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c". However, I believe that this explanation is insufficient as it does not give a clear answer to the question: ""If city a is connected directly with city b, and city b is connected indirectly with city c, then is city a connected indirectly with city c ?"

The true answer in this case is yes and the implication is that a city can belong to one province only (ergo why Union Find is the official solution) -- however one could also reach the conclusion that no, two cities are indirectly connected iff, starting from one, you can reach the other in exactly 2 hops. Therefore, if 2 cities are connected with with at least 3 hops, they are not indirectly connected, and not part of the same province. An implication of this would be that one connected component could have multiple provinces, and one city could belong to multiple provinces.

In that case, the problem would be equivalent to: Find the number of subgraphs such that, any two nodes withn that subgraph are reachable using 2 hops at most.