“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
- 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.
- 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!