Number of Provinces

Q: What is the time complexity of Number of Provinces?

O(n²) with either a graph search or union-find, because both read every entry of the n × n matrix once. Union-find adds a factor α(n), the inverse Ackermann function, which is at most 4 for any real input. The extra space is O(n) for the seen flags, or for the parent and rank arrays.

Q: Should you use DFS, BFS or union-find for Number of Provinces?

All three return the same count in O(n²) time. DFS or BFS is the shortest to write when the whole matrix is given at once. Union-find is the better tool when roads arrive one by one, or when you must also answer whether two cities share a province, because it handles each road and each question in near constant time without a new search.

Q: What do path compression and union by rank do in union-find?

Union by rank attaches the shorter tree under the taller one when two groups merge, which keeps every tree at most log n tall. Path compression makes every node that find passes point straight at the root, so later lookups from those nodes take one step. With both, any sequence of m operations costs O(m α(n)), which behaves like linear time.

Q: How is Number of Provinces different from Number of Islands?

Both count connected components. In Number of Islands the graph is a grid, each square has at most four neighbours, and the work is O(rows × cols). Here the graph comes as an adjacency matrix: any city can link to any other, and you read a full row of n entries to list one city's neighbours.

MediumUnion-find Graphs

+10

There are n cities, numbered from 0 to n-1. You get an n × n matrix isConnected as a list of rows: isConnected[i][j] is 1 when a road links city i and city j directly, and 0 when it does not. Roads work both ways, so the matrix is symmetric, and every city counts as linked to itself.

A province is a group of cities that can all reach each other, directly or through other cities, with no road leading out of the group. Return the number of provinces.

Function

findCircleNum(isConnected: integer-2d-array) → integer

isConnectedinteger-2d-array: the n × n matrix, 1 where a road links two cities directly
Returnsinteger: the number of provinces

Constraints

1 ≤ n ≤ 150, where n = isConnected.length
isConnected[i].length = n
isConnected[i][j] is 0 or 1
isConnected[i][i] = 1
isConnected[i][j] = isConnected[j][i]

Examples

Input: isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
Output: 2
Explanation: City 0 has a road to city 3, and city 1 has a road to city 2. No road crosses between the two pairs, so there are 2 provinces.

+15 hidden tests on Submit

Follow-up

Each road now opens on a given day. Can you find the first day on which all cities belong to a single province?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The matrix is the adjacency matrix of an undirected graph: cities are nodes and a 1 at row i, column j is an edge. A province is a connected component, so the answer is the number of components. The trap is reach through a third city: a 0 between two cities does not put them in different provinces. A search from every unvisited city, or a union-find that merges the two ends of every edge, counts the components in O(n²), the size of the matrix itself.

Depth-first search from every unvisited city

Intuition

Walk through the cities in order. When you meet a city that no earlier search has marked, it cannot belong to a province you already counted, because each search marks its whole province. So add one to the count, then mark every city this one can reach.

To find them, keep a stack. Pop a city, read its row of the matrix, and push every city with a 1 in that row that is not marked yet, marking it as you push. In the second example, the search from city 0 pushes city 1, and city 1's row then adds city 2, even though row 0 has a 0 for city 2. Following rows this way is what catches cities linked only through others.

Each city is popped once, and popping it reads its row of n entries, so the time is O(n²) in total: you read the matrix once. The marks and the stack hold at most n cities, so the extra space is O(n).

A recursive search reads more neatly, but on a province shaped like one long line the calls nest once per city. At n = 150 that is safe; the same code on a graph with 10^5 nodes overflows the call stack, so the explicit stack is the habit worth keeping.

Algorithm

Make a seen flag for every city and set the count to 0.
Go through the cities in order and skip any city already seen.
On an unseen city, add 1 to the count, mark it and push it on a stack.
While the stack has cities, pop one and push every city in its row that has a 1 and is not seen yet, marking it as you push.
Return the count.

def findCircleNum(isConnected):
    n = len(isConnected)
    seen = [False] * n
    provinces = 0
    for start in range(n):
        if seen[start]:
            continue
        # Nobody reached this city from an earlier province, so it starts a new one.
        provinces += 1
        seen[start] = True
        stack = [start]
        while stack:
            city = stack.pop()
            row = isConnected[city]
            for other in range(n):
                # Mark a city when you push it, so it is never pushed twice.
                if row[other] == 1 and not seen[other]:
                    seen[other] = True
                    stack.append(other)
    return provinces

Union-find with path compression and union by rank

Intuition

Turn the question around. Start with n provinces, one per city. Every 1 in the matrix says two cities belong together: if they are still in different groups, merge the groups, and the count drops by one. After the last road the count is the answer. You only need the entries above the diagonal, because the matrix is symmetric and the diagonal links a city to itself. In the second example the count starts at 5. The 1 at (0, 1) merges cities 0 and 1 (4 left), and the 1 at (1, 2) finds that city 1 belongs to city 0's group and brings city 2 into it (3 left). Cities 3 and 4 have no 1 above the diagonal, so the answer is 3.

A union-find, also called a disjoint set union, stores each group as a tree. parent[c] points one step up, and the city at the top, whose parent is itself, is the group's root. Two cities are in the same group exactly when find walks both up to the same root. To merge two groups, point one root at the other.

Two rules keep the trees flat. Union by rank hangs the shorter tree under the taller one, so a tree of height h holds at least 2^h cities and no path is longer than log n. Path compression goes further: once find has located the root, it points every city it passed straight at that root, so the next lookup from any of them takes one step. Without either rule, merging the cities of a long chain in an unlucky order builds a tree that is a single path, and every find walks O(n) steps.

With both rules, each find costs amortized O(α(n)), where α is the inverse Ackermann function, which stays at most 4 for any n a computer can hold. Reading the matrix still costs O(n²), so that is the total, and the parent and rank arrays take O(n) space. The structure earns its place when roads arrive one at a time: it keeps the count current after each new road without searching again.

Algorithm

Set parent[c] = c and rank[c] = 0 for every city, and the count to n.
For every pair i < j with isConnected[i][j] = 1, find the roots of i and j.
In find, walk up to the root, then walk the same path again and point each city on it straight at the root.
If the roots differ, attach the root of lower rank under the other one, add 1 to the rank on a tie, and subtract 1 from the count.
Return the count.

def findCircleNum(isConnected):
    n = len(isConnected)
    parent = list(range(n))
    rank = [0] * n

    def find(city):
        root = city
        while parent[root] != root:
            root = parent[root]
        # Path compression: point every city on the way straight at the root.
        while parent[city] != root:
            up = parent[city]
            parent[city] = root
            city = up
        return root

    provinces = n
    for i in range(n):
        for j in range(i + 1, n):  # the matrix is symmetric, so the upper half is enough
            if isConnected[i][j] == 1:
                a, b = find(i), find(j)
                if a == b:
                    continue
                # Union by rank: hang the shorter tree under the taller one.
                if rank[a] < rank[b]:
                    a, b = b, a
                parent[b] = a
                if rank[a] == rank[b]:
                    rank[a] += 1
                # Two provinces just became one.
                provinces -= 1
    return provinces

Pitfalls and edge cases

Most wrong answers treat a 0 as proof that two cities are apart, or count something other than components.

Checking only direct roads. Cities 0 and 2 in the second example have a 0 between them and still share a province through city 1. Any count built from direct roads alone misses that; counting the distinct rows, for example, gives 5 there instead of 3.
Counting the 1s and dividing by two. That counts roads, not provinces: three cities that all link to each other have three roads and one province.
In union-find, lowering the count on every 1 instead of only when the two roots differ. A road inside a group that is already merged must not change the count.
Comparing parents instead of roots. parent[i] == parent[j] can be false for two cities in the same group when one sits deeper in the tree; always compare find(i) with find(j).
Attaching city j itself instead of its root, as in parent[j] = find(i). If j was already in a group, the rest of that group is cut off from the merge.
Recursion on large graphs. A recursive search, or a recursive find without union by rank, goes one level per city on a chain shaped graph. That is fine at 150 cities and a stack overflow at 10^5.

Frequently asked questions4

What is the time complexity of Number of Provinces?

O(n²) with either a graph search or union-find, because both read every entry of the n × n matrix once. Union-find adds a factor α(n), the inverse Ackermann function, which is at most 4 for any real input. The extra space is O(n) for the seen flags, or for the parent and rank arrays.

Should you use DFS, BFS or union-find for Number of Provinces?

All three return the same count in O(n²) time. DFS or BFS is the shortest to write when the whole matrix is given at once. Union-find is the better tool when roads arrive one by one, or when you must also answer whether two cities share a province, because it handles each road and each question in near constant time without a new search.

What do path compression and union by rank do in union-find?

Union by rank attaches the shorter tree under the taller one when two groups merge, which keeps every tree at most log n tall. Path compression makes every node that find passes point straight at the root, so later lookups from those nodes take one step. With both, any sequence of m operations costs O(m α(n)), which behaves like linear time.

How is Number of Provinces different from Number of Islands?

Both count connected components. In Number of Islands the graph is a grid, each square has at most four neighbours, and the work is O(rows × cols). Here the graph comes as an adjacency matrix: any city can link to any other, and you read a full row of n entries to list one city's neighbours.

Python

def findCircleNum(isConnected):
    # Write code here

Test cases

Case 1

Case 2

Input

isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]

Expected