• 1 <= n <= 200
• isConnected[i][j] is 0 or 1
• isConnected[i][i] == 1 for every i
• isConnected[i][j] == isConnected[j][i] — the relation is symmetric
• Connections are transitive: reachability through intermediates counts

The word "province" is decoration. Cities are vertices, connections are undirected edges, and a province is a connected component — a maximal group of mutually reachable vertices. The task is to count them, which is one of the most standard operations in graph work, and there are two clean ways to do it that are worth knowing side by side.

The matrix is an adjacency matrix: entry (i, j) records whether an edge joins city i and city j. Two properties are given and both matter.

It is symmetric, so entry (i, j) always equals entry (j, i). That confirms the graph is undirected and means you only ever need to look at one triangle of the matrix — scanning j from i+1 upward visits each pair exactly once.

The diagonal is all 1s, meaning each city is connected to itself. That is a formality carrying no information, and it never merges two distinct cities.

One consequence to notice before choosing an algorithm: finding the neighbours of city i means scanning an entire row of n entries, whether that city has 100 connections or none. So any approach costs at least O(n²) simply to read the input. The algorithm cannot be faster than the format.

Walk through the cities in order. When you find one not yet visited, you have found a province nobody has counted — so add one to the total, and then traverse that entire province, marking every city in it as visited. When the outer loop later reaches those cities, they are already marked and are skipped.

The two loops have completely separate jobs, and keeping that straight is the key to the pattern. The outer loop finds a starting point in an as-yet-undiscovered province and does the counting. The inner traversal consumes exactly one province so that it can never be counted twice.

def find_circle_num(is_connected):
    n = len(is_connected)
    visited = [False] * n

    def visit(city):
        visited[city] = True
        for other in range(n):
            if is_connected[city][other] == 1 and not visited[other]:
                visit(other)

    provinces = 0
    for city in range(n):
        if not visited[city]:
            provinces += 1          # a province no traversal has reached
            visit(city)             # consume all of it
    return provinces

Cost: the traversals together enter each city once, and each entry scans a full row of n entries, so the total is O(n²) time with O(n) space. Note the inner loop runs over every column even when almost all are zeros — that is the matrix format, not a flaw in the algorithm. Breadth-first search with a queue would visit exactly the same cities at the same cost; there is no distance in this question, so the traversal order is irrelevant and depth-first is simply shorter.

The other route never traverses anything. Start by assuming the worst — n cities, n separate provinces — and then merge.

Scan the upper triangle of the matrix. For each connection found, attempt to merge the two cities' groups. If they were already in the same group the connection tells you nothing new. If they were in different groups, two provinces just became one, so decrement the count.

This uses Union-Find, which maintains for each element a pointer toward a representative of its group. Two cities are in the same province exactly when they share a representative, and merging two groups costs a single pointer write.

def find_circle_num(is_connected):
    n = len(is_connected)
    parent = list(range(n))
    rank = [0] * n
    provinces = n                             # start pessimistic: all separate

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]     # flatten while walking
            x = parent[x]
        return x

    for i in range(n):
        for j in range(i + 1, n):             # upper triangle only
            if is_connected[i][j] == 1:
                ri, rj = find(i), find(j)
                if ri != rj:                  # a genuine merge
                    if rank[ri] < rank[rj]:
                        ri, rj = rj, ri
                    parent[rj] = ri
                    if rank[ri] == rank[rj]:
                        rank[ri] += 1
                    provinces -= 1
    return provinces

Cost: O(n² · α(n)), effectively O(n²), with O(n) space.

Take isConnected = [[1,1,0],[1,1,1],[0,1,1]] — city 0 joined to 1, city 1 joined to 2, and 0 not joined to 2 directly.

By traversal. City 0 is unvisited, so provinces becomes 1 and visit(0) runs. It marks 0 and scans row 0, finding a 1 at column 1, so it recurses into city 1. That marks 1 and scans row 1, finding 1s at columns 0 — already visited, skip — and 2, so it recurses into city 2. City 2 marks itself and scans row 2, finding a 1 at column 1, already visited. Everything unwinds. The outer loop then reaches cities 1 and 2, both already marked, and skips them. Answer 1.

By merging. Start with provinces = 3 and each city its own root.
- Pair (0,1) is connected. Roots 0 and 1 differ, so merge and provinces drops to 2.
- Pair (0,2) is not connected. Nothing happens.
- Pair (1,2) is connected. find(1) returns the merged root, find(2) returns 2, they differ, so merge and provinces drops to 1.

Answer 1. Note that cities 0 and 2 were never compared directly and are still correctly in one province — transitivity is handled by the group structure rather than by any explicit check.

Now the isolated case [[1,0,0],[0,1,0],[0,0,1]]. The traversal launches three times, each consuming a single city, giving 3. The merge version finds no off-diagonal 1s, performs no merges, and returns the initial 3.

Both are optimal here, so the choice is about what the surrounding problem looks like.

Traversal is the better default when the graph is given as a matrix or adjacency list and asked about once. It is shorter, needs no auxiliary structure, and extends naturally when you want more than a count — the size of each province, the members of each, the largest one.

Union-Find wins when connections arrive over time and the count must be reported after each addition. A traversal would have to rerun from scratch after every new road; the merge version updates in effectively constant time. It is also the natural fit when the input is an edge list rather than a matrix.

The recognition signal for both is broad and common: counting connected components. It appears as provinces, friend circles, islands in a grid, groups of accounts to merge, clusters of related items. The underlying shape is always the same — find something not yet claimed, claim everything reachable from it, and count how many times you had to begin again.

Train the reflex: when asked how many separate groups exist, do not try to reason about the groups. Consume one at a time and count the restarts — or start with everything separate and count the merges.