Number of Provinces

Problem

There are n cities. isConnected is an n × n matrix where isConnected[i][j] = 1 if city i and city j are directly connected, 0 otherwise (this is a graph given as an adjacency matrix, and the "direct connection" relation is symmetric — undirected). A province is a group of directly-or-indirectly connected cities. Return the total number of provinces. (LeetCode 547.)

Examples

Constraints

1 ≤ n ≤ 200.

Attempt it first

Strip away the "cities and provinces" framing: this is asking for the number of connected components in an undirected graph — a question this module has two entirely different correct tools for. Before opening anything, solve it with the traversal approach from the DFS & BFS concept lesson (visit an unvisited node, flood-fill mark its whole component, increment a counter, repeat). Then, separately, work out how Union-Find would answer the exact same question, so you can compare both approaches on the same problem below.