871. Number of Provinces
Medium•
You are given an n × n symmetric matrix isConnected. An entry of 1 means those two cities are directly connected; 0 means they are not. Each city is connected to itself.
A province is one maximal group of cities reachable from one another through direct or indirect connections. Return the number of provinces. An isolated city is a province of its own.
Do not modify the matrix. Matrix rows describe cities and columns describe neighbors; this is a graph adjacency matrix, not a grid traversal problem.
Example 1:
Input: findCircleNum([[1, 1, 0], [1, 1, 0], [0, 0, 1]])
Output: 2
Explanation: Cities 0 and 1 form one province; city 2 forms another.
Example 2:
Input: findCircleNum([[1, 0, 0], [0, 1, 0], [0, 0, 1]])
Output: 3
Explanation: Each city is isolated from the others, giving three provinces.
Example 3:
Input: findCircleNum([[1]])
Output: 1
Explanation: A single city is one province.
Constraints
- 1 <= n <= 200
- The matrix has n rows and n columns.
- All entries are 0 or 1.
- isConnected[i][i] == 1
- isConnected[i][j] == isConnected[j][i]
Accepted3/4|Acceptance Rate75.0%