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

The title

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 or 0 isConnected[I][I] == 1 isConnected[i][j] == isConnected[j][i]Copy the code

Source: LeetCode leetcode-cn.com/problems/nu…

Their thinking

  1. In the two-dimensional array, isConnected[I][j] = 1 indicates that the ith city and the j city are directly connected, and the connected cities are merged into the set and searched.

Example:

[1,1,0], [0,0,1]Copy the code

IsConnected [I][J].

  • When I =0 and j=0, 0 is connected to 0; when I =1 and j=1, 1 is connected to 1; when I =2 and j=2, 2 is connected to 2.
  • The upper right part of the diagonal is completely symmetric with the lower left part. Let’s look at the connection of the upper right part:
    • I =0 and j=1 connect 0 and 1
    • When I =0 and j=2, 0 and 2 are disconnected
    • When I =1 and j=2, 1 and 2 are disconnected

    0 is connected to 1, 2 is not connected, so there are two provinces.

  1. The number of provinces is equal to the number of connected relationships, that is, the number of nodes in the set whose parent node is its own.

Code implementation

var findCircleNum = function (isConnected) {
    const n = isConnected.length
    const u = new UnionSet(n)

    // merge the city connections into the query set
    // The number of provinces equals the number of connected relationships
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (isConnected[i][j] === 1) u.merge(i, j)
        }
    }

    let ans = 0

    // Check the number of parent nodes in the set
    for (let i = 0; i < n; i++) {
        if (u.get(i) === i) ans++
    }

    return ans
};

class UnionSet {
    constructor(n) {
        // Initializes an array of parent nodes, each of which defaults to its own parent
        this.pa = new Array(n + 1).fill(0).map((item, index) = > index)

        // Initialize the number of nodes per tree
        this.size = new Array(n + 1).fill(1)}get(x) {
        // Find the parent node of x and complete the path optimization
        // After optimization, the parent of x points to the root of the tree
        return this.pa[x] = this.pa[x] === x ? x : this.get(this.pa[x])
    }

    merge(a, b) {
        // Find the root node of A
        const ra = this.get(a)
        // find the root node of b
        const rb = this.get(b)

        // If a and B are in the same set, there is no need to merge
        if (ra === rb) return

        // Merge the set with a small number of nodes into a large number of nodes
        // Update the sum of nodes A and B
        if (this.size[ra] < this.size[rb]) {
            this.pa[ra] = rb
            this.size[rb] += this.size[ra]
        } else {
            this.pa[rb] = ra
            this.size[ra] += this.size[rb]
        }
    }
}
Copy the code

If there are mistakes welcome to point out, welcome to discuss together!