Number of Provinces

Medium· Union-Find· DFS

Problem

You are given an n x n adjacency matrix where isConnected[i][j] = 1 means cities i and j are directly linked. A province is a group of cities connected directly or indirectly. Return the number of provinces.

Examples

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Output: 2

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]

Output: 3

Constraints

• 1 <= n <= 200
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

Hints & approach

Hint 1

A province is a connected component.

Hint 2

Start with n separate groups and merge whenever two cities are linked.

Hint 3

With union-find, every successful union reduces the component count by one.

Approachtry the hints first

Initialize a disjoint-set structure with n components. For every pair i < j with isConnected[i][j] = 1, union the two cities; when their roots differ, decrement the component count. Path compression and union by rank keep each operation nearly constant. A DFS from every unvisited city, counting how many DFS starts you make, gives the same answer.

Time O(n^2 * α(n)) · Space O(n)

← PreviousCourse Schedule II Next →Redundant Connection