“This is the 25th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Topic link

547. Number of Provinces – LeetCode (leetcode-cn.com)

Topic describes

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.

The test case

Example 1:

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

conditions

1 <= N <= 200 N == isConnected. Length N == isConnected[I]. Length isConnected[I][j] : 1 or 0 isConnected[I][I] == 1 isConnected[i][j] == isConnected[j][i]Copy the code

Subject analysis

They will give us an n by n matrix, isConnected[I][j] = 1 means I isConnected to j. If multiple points are connected, then the points are combined into a group, that is, there may be one point in a group, or there may be multiple points. They want us to figure out how many groups of nodes there are in a given two-dimensional array

An appropriate way to do this is to use a let Used = new Set() to record the points traversed and count to record how many group nodes there are

The array is traversed as follows:

  1. from[0] [0]Starting with the subscript, left to right, top to bottom, start traversing;
  2. When traversing I, if there are coordinates of value one, for exampleisConnected[i][j] = 1If j does not exist in the traversalused, then add the JTH line to the node to be traversed; If there’s also something in row j that doesn’t existusedAdds the corresponding row to the traversed array
  3. When the breadth search is complete,countAdd 1
  4. After completing the above steps, proceed from noi+1Line begins to repeat steps 2,3,4 (ifi+1There areused, repeat the preceding steps starting from the next line

Code implementation

/ * * *@param {number[][]} isConnected
 * @return {number}* /
var findCircleNum = function(isConnected) {
    let used = new Set(a);let count = 0;
    for (let i = 0; i < isConnected.length; i++) {
        if (used.has(i)) {
            continue;
        }
        count++;
        let arrs = [i];
        while (arrs.length > 0) {
            let curr = arrs.shift();
            for (let j = 0; j < isConnected[curr].length; j++) {
                if(! used.has(j) && isConnected[curr][j] ==1) { arrs.push(j); used.add(j); }}}}return count;
};

Copy the code

Use “Used” to quickly filter out already traversed rows

Considering the mapping relationship of the two-dimensional array form, the coordinates of the upper right and lower left of the two-dimensional array are symmetric along the diagonal line, we only need to traverse the upper right or lower left part of the two-dimensional array