The title

547. Number of provinces

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

Idea 1:

Depth-first search of charts

  1. The length of isConnected represents the total number of cities
  2. Declare a Set object visited, which is used to store the city traversed and the city connected to the current city. This kind of recorded cities will be skipped after sequential traversal.
  3. Declare a counter count for the number of provinces
  4. Traverse every city in isConnected,
    • If the current city I has not been traversed, then recursive depth search,
    • If it is found that city J is connected to CITY I, and city J has not been recorded by Visted, city J is put into Visted.
    • Recursively, we look for city J, see if there are any other cities connected to it, until there are none, and count+1
  5. So I’m just going to return this count

The code is as follows:

/ * * *@param {number[][]} isConnected
 * @return {number}* /
var findCircleNum = function(isConnected) {
    let cityNum = isConnected.length;
    let visited = new Set(a);let count = 0;
    for(let i=0; i<cityNum; i++){if(! visited.has(i)){ dfs(isConnected,visited,cityNum,i); count++ } }return count;
};

function dfs(isConnected,visited,cityNum,i){
    for(let j=0; j<cityNum; j++){if(isConnected[i][j] == 1 && !visited.has(j)){
            visited.add(j);
            dfs(isConnected,visited,cityNum,j)
        }
    }
}
Copy the code

Complexity analysis:

Time complexity: O(n^2), the need to traverse every city, and then to traverse all cities, can be equivalent to the cycle cycle.

Space complexity: O(n), where vistedCity stores n cities, and the depth of recursive call stack does not exceed N.

Idea 2:

Breadth-first search for charts

  1. The length of isConnected represents the total number of cities
  2. Declare a Set object visited, which is used to store the city traversed and the city connected to the current city. This kind of recorded cities will be skipped after sequential traversal.
  3. Declare a counter count for the number of provinces
  4. Declares a queue to store the cities to be processed
  5. Traverse isConnected
    • If the current city I has not been processed, it is enqueued
    • Take out the head element from the queue and put the current city into visited.
    • Go through isConnected again, if any city isConnected to the current city, put it in the queue
    • As long as the queue is not empty, it will continue to be processed until the queue is empty. Then count+1 means that all cities connected with city I have been included in the visited
  6. Finally, return count, the number of provinces

The code is as follows:

/ * * *@param {number[][]} isConnected
 * @return {number}* /
var findCircleNum = function(isConnected) {
    let cityNum = isConnected.length;
    let visited = new Set(a);let count = 0;
    let queue = [];
    for(let i=0; i<cityNum; i++){if(! visited.has(i)){ queue.push(i);while(queue.length>0) {let j = queue.shift();
               visited.add(j);
               for(let k=0; k<isConnected.length; k++){if(isConnected[j][k] == 1&&! visited.has(k)){ queue.push(k) } } } count++; }}return count;
};
Copy the code

Complexity analysis

Time complexity: O(n^2), essentially every city is compared to all cities, which is n*n;

Spatial complexity: O(n), we need to use Visited to record all the cities, that is, N; in addition, the length of the queue is at most N.

Idea 3:

Check and set

We can make use of and look up the data structure of the set. The initial connecting flux is the length of isConnected. If two cities are connected, the two cities will be connected and the connecting flux will be calculated finally.

Here first to understand and check what is set, recommended to see these two articles, very good.

Name1e5s # Most easy to understand and check the collection of details by Chuancey

  1. Create a parent array to record the connections between cities and initialize the parent element to point to itself
  2. Create a continuous flux count to record how many sets there are
  3. Create the join method union that points the root node of one node to the root node of another node
  4. Create a method called find to find the root node, which uses path compression and flattening, so that in each set, all elements except the root node are on the same level.
  5. Traverses the isConnected array to determine if two cities are adjacent, and if they are, join the two nodes in the parent array
  6. Iterate over parent, and if the node is the same, count++
  7. Returns the continuous flux count

The code is as follows:

/ * * *@param {number[][]} isConnected
 * @return {number}* /
var findCircleNum = function(isConnected) {
    let count = 0;
    let len = isConnected.length;
    // Handle the parent array. When initialized, each element points to itself
    let parent = new Array(len).fill(0).map((item,index) = >index)
    for(let i=0; i<len; i++){for(let j=i+1; j<len; j++){// Check I and j, if connected, then join them
            if(isConnected[i][j] == 1){ union(parent,i,j); }}}for(let i=0; i<parent.length; i++){if(parent[i] == i){ count++; }}return count;
};

function union(parent,p,q){
    // connect p and q to the root node of q and vice versa
    let rootP = find(parent,p);
    let rootQ = find(parent,q);
    parent[rootP] = rootQ;
}

function find(parent,x){
    // Find the root node of x, and compress the path, take the found root node as the parent node of x
    if(parent[x] ! = x){ parent[x] = find(parent,parent[x]) }return parent[x];
}

Copy the code

Complexity analysis

Time complexity: O(n^2logn), traversal isConnected is n^2, traversal at the same time, merge and search, merge into O(1), search we use path optimization here, find the parent node time complexity is logn, so the total is O(n^2logn).

It is recommended to take a look at the big guy’s analysis of set time complexity

# And look up the time complexity of sets in various cases

Space complexity: O(n),parent Stores the parent of all nodes.