Connected City Regions

MEDIUM20 pts

You are given a network of n cities. Some cities have direct routes connecting them, while others do not. The connectivity between cities follows a transitive relationship: if city A has a direct route to city B, and city B has a direct route to city C, then cities A, B, and C are all considered to be within the same interconnected region, even if there is no direct route between A and C.

A region is defined as a maximal group of cities where every city in the group can reach every other city in the same group through some sequence of direct routes. Cities that cannot reach each other (directly or indirectly) belong to different regions.

You are provided with an n × n adjacency matrix called adjacencyMatrix where:

adjacencyMatrix[i][j] = 1 indicates that city i and city j have a direct route connecting them
adjacencyMatrix[i][j] = 0 indicates that there is no direct route between city i and city j

Properties of the adjacency matrix:

The matrix is symmetric: adjacencyMatrix[i][j] == adjacencyMatrix[j][i] (routes are bidirectional)
Every city connects to itself: adjacencyMatrix[i][i] == 1

Your task is to determine the total number of distinct regions in the city network.

Example

Input

adjacencyMatrix = [[1,1,0],[1,1,0],[0,0,1]]

Output

2

Explanation

There are 3 cities in the network. City 0 and City 1 are directly connected (both adjacencyMatrix[0][1] and adjacencyMatrix[1][0] equal 1), forming one region. City 2 has no direct routes to any other city, so it forms its own isolated region. Therefore, there are 2 distinct regions in total.

Example

Input

adjacencyMatrix = [[1,0,0],[0,1,0],[0,0,1]]

Output

3

Explanation

There are 3 cities, but no city has a direct route to any other city (all off-diagonal entries are 0). Each city is completely isolated and forms its own region. Therefore, there are 3 distinct regions.

Example

Input

adjacencyMatrix = [[1,1,1],[1,1,1],[1,1,1]]

Output

1

Explanation

All 3 cities are directly connected to each other. Every pair of cities has a direct route between them, so all cities belong to the same region. Therefore, there is only 1 region.

Accepted0/0·0% Acceptance

Constraints

1 ≤ n ≤ 200
n == adjacencyMatrix.length
n == adjacencyMatrix[i].length
adjacencyMatrix[i][j] is either 0 or 1
adjacencyMatrix[i][i] == 1 (every city connects to itself)
adjacencyMatrix[i][j] == adjacencyMatrix[j][i] (symmetric matrix)

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

isConnected =

[[1,1,0],[1,1,0],[0,0,1]]

Connected City Regions

Hints

Connected City Regions

Hints