Show problems as
Classic problem #547MediumDepth-First SearchBreadth-First SearchUnion-FindGraph Theory

Number of Provinces

Real-world version: Count the Sensor Meshes
Tracked in this browser only
Read Number of Provinces on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstFinding Connected Components · Graphs, animated step by step

A field crew scatters n battery-powered sensors across a valley and reads off which pairs of them can hear each other over the radio. The readings arrive as an n x n grid linked, where linked[i][j] is 1 when sensor i and sensor j exchange packets straight across and 0 when they do not. Hearing is mutual, so the grid reads the same either way round, and every sensor hears itself, so the diagonal is all 1.

Traffic can be relayed. If sensor i reaches sensor j straight across, and sensor j reaches sensor k straight across, then anything sensor i sends can still land at sensor k by way of j, and chains of relays can run as long as they like.

Call a mesh a group of sensors that can all get traffic to one another over some chain of hops, and that cannot be widened: no sensor left outside the group is able to join in. A sensor that hears nobody at all forms a mesh on its own.

Return how many meshes the crew has deployed.

Examples

Example 1

Input
linked = [[1, 1, 0, 0, 0], [1, 1, 0, 1, 0], [0, 0, 1, 0, 1], [0, 1, 0, 1, 0], [0, 0, 1, 0, 1]]
Output
2

Sensors 0, 1 and 3 sit in one mesh, since 0 gets traffic to 3 by way of 1. Sensors 2 and 4 hear each other and make up the other. All five sensors are accounted for.

Example 2

Input
linked = [[1, 1, 0, 1], [1, 1, 1, 0], [0, 1, 1, 1], [1, 0, 1, 1]]
Output
1

Every sensor reaches every other one along the ring of hops 0-1, 1-2, 2-3, 3-0, so the four of them form a single mesh.

Example 3

Input
linked = [[1, 0, 1, 0, 0, 0], [0, 1, 0, 0, 1, 0], [1, 0, 1, 0, 0, 1], [0, 0, 0, 1, 0, 0], [0, 1, 0, 0, 1, 0], [0, 0, 1, 0, 0, 1]]
Output
3

Sensors 0, 2 and 5 chain together, sensors 1 and 4 pair up, and sensor 3 hears nobody, which still counts as a mesh of one.

Constraints

  • 1 <= n <= 200
  • n == linked.length
  • n == linked[i].length
  • linked[i][j] is 1 or 0.
  • linked[i][i] == 1
  • linked[i][j] == linked[j][i]

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_the_sensor_meshes(linked: list[list[int]]) -> int:
Java
public int countTheSensorMeshes(int[][] linked)

More on the same topics