547. Number of provinces
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: 2
Example 2:
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]
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]
Code implementation
/** * @param {number[][]} isConnected * @return {number} */ var findCircleNum = function(isConnected) { const len = isConnected.length const uf = new UinoFind(len) for(let i = 0; i < len; i++){ for(let j = i + 1; j < len; If (isConnected[I][j] == 1){uf.unite(I,j)}}} return uf.getcount ()}; Constructor (n){this.parent = new Array(n).fill(0).map((value,index) => index) This.rank = new Array(n).fill(1) this.setCount = n} findSet(index){if(this.parent[index]! = index){ this.parent[index] = this.findSet(this.parent[index]) } return this.parent[index] } unite(index1,index2){// Let root1 = this.findSet(index1) let root2 = this.findSet(index2) if(root1! = root2){if(root1 < root2){[root1,root2] = [root2,root1]} // Merge the root node this.parent[root2] = root1 // count the number of nodes that have been merged This. Rank [root1] +=this. Rank [root2] // Add one city to this. Connected (index1,index2){// connected(index1,index2){ Let root1 = this.findSet(index1) let root2 = this.findSet(index2) return root1 == root2}}Copy the code