Tap here to switch tabs
Problem
Submissions

Problem: Number of Provinces

Number of Provinces gives a city connection matrix where direct links can join larger groups through indirect connections. Return the total number of provinces.

Statement

Given nn cities, some are directly connected, and others are not. You are given an n×nn \times n matrix called cities, where cities[i][j] =1= 1 means city ithi^{th} and city jthj^{th} are directly connected, and cities[i][j] =0= 0 means they are not directly connected.

Note: If city AA is directly connected to city BB and city BB is directly connected to city CC, then city AA is indirectly connected to city CC.

The task is to return the total number of groups of connected cities directly or indirectly. These groups are referred to as provincesA province is a group of directly or indirectly connected cities with no other cities outside of the group..

Constraints:

  • 1≤1\leq nn ≤200\leq200

  • n==n == cities.length

  • n==n == cities[i].length, where 0≤0\leq ii ≤n\leq n

  • cities[i][j] is either 00 or 11.

  • cities[i][i] ==1== 1

  • cities[i][j] ==== cities[j][i]

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Number of Provinces

Number of Provinces gives a city connection matrix where direct links can join larger groups through indirect connections. Return the total number of provinces.

Statement

Given nn cities, some are directly connected, and others are not. You are given an n×nn \times n matrix called cities, where cities[i][j] =1= 1 means city ithi^{th} and city jthj^{th} are directly connected, and cities[i][j] =0= 0 means they are not directly connected.

Note: If city AA is directly connected to city BB and city BB is directly connected to city CC, then city AA is indirectly connected to city CC.

The task is to return the total number of groups of connected cities directly or indirectly. These groups are referred to as provincesA province is a group of directly or indirectly connected cities with no other cities outside of the group..

Constraints:

  • 1≤1\leq nn ≤200\leq200

  • n==n == cities.length

  • n==n == cities[i].length, where 0≤0\leq ii ≤n\leq n

  • cities[i][j] is either 00 or 11.

  • cities[i][i] ==1== 1

  • cities[i][j] ==== cities[j][i]