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 in practice. The extra space is O(n).

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. Union-find is the better tool when you must also answer many questions of the form "do these two cities share a province", because each answer takes near constant 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 is an adjacency matrix: any city can link to any other, and listing one city's neighbours reads a full row of n entries.

MediumUnion-find Graphs

+10

There are n cities, numbered 0 to n-1. isConnected[i][j] is 1 when a road links city i and city j directly, and 0 otherwise. Roads work both ways, so the matrix is symmetric, and every city is 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.

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 describes an undirected graph: cities are nodes and each 1 is an edge. A province is a connected component, and a 0 between two cities does not separate them when a third city links both. A search from every unvisited city, or a union-find over every edge, counts the components in O(n²).

Depth-first search from every unvisited city

Intuition

An unmarked city cannot belong to a province you already counted, because each search marks its whole province. So it starts a new one. The search follows rows of the matrix: in the second example, the search from city 0 reaches city 1, and city 1's row then reaches city 2, although row 0 has a 0 for city 2.

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

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

Start with n provinces, one per city. Each 1 above the diagonal says two cities belong together: if their groups differ, merge them and lower the count by one. In the second example the count starts at 5, (0, 1) merges cities 0 and 1, (1, 2) brings city 2 into their group, and 3 provinces are left.

Union-find stores each group as a tree: parent[c] points one step up, and two cities share a group when find walks both to the same root. Left alone, merges can build one long path that every find walks in O(n) steps. Union by rank hangs the shorter tree under the taller, so no path is longer than log n. Path compression points every city find passed straight at the root. Together they make each find amortized O(α(n)), and α(n) is at most 4 in practice.

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 path again and point each city on it at the root.
If the roots differ, attach the root of lower rank under the other, 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

Trusting direct roads only. Cities 0 and 2 in the second example have a 0 between them and still share a province.
Counting the 1s and dividing by two. 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.
Comparing parent[i] with parent[j]. Two cities in one group can have different parents when one sits deeper; compare find(i) with find(j).
Attaching city j itself, as in parent[j] = find(i). If j was already in a group, the rest of that group is left out of the merge.

Frequently asked questions3

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 in practice. The extra space is O(n).

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. Union-find is the better tool when you must also answer many questions of the form "do these two cities share a province", because each answer takes near constant 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 is an adjacency matrix: any city can link to any other, and listing one city's neighbours reads a full row of n entries.

def findCircleNum(isConnected):
    # Write code here

Test #1

Test #2

Argument

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

Expected Output