[B] [C] [D]

There are n cities, some of which are connected to each other, some of which are not. If city A is directly connected to city B, and city B is directly connected to city C, then city A is indirectly connected to city C.

A province is a group of directly or indirectly connected cities that do not contain other unconnected cities.

IsConnected [I][j] = 1 indicates that the ith city and the j city are directly connected, and isConnected[I][j] = 0 indicates that the two are not directly connected.

Returns the number of provinces in the matrix.

Example 1:

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]] output: 2Copy the code

Example 2:

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]Copy the code

Tip:

  • 1 <= n <= 200
  • n == isConnected.length
  • n == isConnected[i].length
  • isConnected[i][j] 为 1 或 0
  • isConnected[i][i] == 1
  • isConnected[i][j] == isConnected[j][i]

Their thinking

This is a connectivity problem.

  1. Create an array of tags and initialize each city to mark unprocessed.
  2. Traverses the input array and skips if the current city has been processed. Otherwise, a new city is found, and the city must belong to a province, so the number of provinces +1.
  3. Mark the cities in Step 2 as processed and traverse the array of cities to try to connect to other cities. If they can connect, mark them as processed.
  4. Finally, when the input array is iterated, we get all the provinces.

The demo

Code implementation

Var findCircleNum = function(isConnected) { Const len = isConnected. Length, // Initialize the tag Array tag = Array(len).fill(false); // Let res = 0; // iterate over the input array for(let I = 0; i<len; If (tag[I]) continue; if(tag[I]) continue; // if a new city is found, it must belong to a new province, so the number of provinces +1 res++; // Handle the current city (I); } function handle(I){tag[I] = true; For (let j = 0; j<len; j++){ if(j===i||tag[j]||isConnected[i][j]===0) continue; handle(j) } } return res; };Copy the code

At this point we are done with Leetcode -547- number of provinces

If you have any questions or suggestions, please leave a comment!