#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/union-find/problem-number-of-provinces

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/union-find/problem-number-of-provinces

Repovive

Problem - Number of Provinces - Union-Find | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units

Open in Course

Problem - Number of Provinces

Friend circles as components

Given an $n \times n$ matrix isConnected where isConnected[i][j] = 1 means city $i$ and city $j$ are directly connected, return the number of provinces.

A province is a group of directly or indirectly connected cities. Example:

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

Returns $2$ (cities 0,1 form one province; city 2 alone).

You're finding connected components on an adjacency matrix. Constraints: $n$ from $1$ to $200$ .

HannahHi! I'm Hannah. Let me know if you need help understanding anything!