当前位置:网站首页>Leetcode (547) - number of provinces
Leetcode (547) - number of provinces
2022-07-07 00:44:00 【SmileGuy17】
Leetcode(547)—— Number of provinces
subject
Yes n n n Cities , Some of them are connected to each other , Others are not connected . If the city a a a And the city b b b Direct connection , And the city b b b And the city c c c Direct connection , So the city a a a And the city c c c Indirectly connected .
Province It's a group of directly or indirectly connected cities , There are no other cities in the group that are not connected .
To give you one n × n n \times n n×n Matrix i s C o n n e c t e d isConnected isConnected, among i s C o n n e c t e d [ i ] [ j ] = 1 isConnected[i][j] = 1 isConnected[i][j]=1 It means the first one i i i Two cities and j j j The two cities are directly connected , and i s C o n n e c t e d [ i ] [ j ] = 0 isConnected[i][j] = 0 isConnected[i][j]=0 The two are not directly connected .
Back in the matrix Province The number of .
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]]
Output :3
Tips :
- 1 1 1 <= n <= 200 200 200
- n == isConnected.length
- n == isConnected[i].length
- isConnected[i][j] by 1 1 1 or 0 0 0
- isConnected[i][i] == 1 1 1
- isConnected[i][j] == isConnected[j][i]
Answer key
Method 1 :DFS
Ideas
The idea of depth first search is very intuitive . Traverse all cities , For every city , If the city has not been visited , Then start the depth first search from the city , Through the matrix isConnected \textit{isConnected} isConnected Get what cities are directly connected to the city , These cities and the city belong to the same connected component , Then continue the depth first search for these cities , Until all cities of the same connected component are visited , You can get a province . After traversing all the cities , You can get the total number of connected components , That is, the total number of provinces .
Code implementation
Leetcode Official explanation ( recursive ):
class Solution {
public:
void dfs(vector<vector<int>>& isConnected, vector<int>& visited, int cities, int i) {
for (int j = 0; j < cities; j++) {
if (isConnected[i][j] == 1 && !visited[j]) {
visited[j] = 1;
dfs(isConnected, visited, cities, j);
}
}
}
int findCircleNum(vector<vector<int>>& isConnected) {
int cities = isConnected.size();
vector<int> visited(cities);
int provinces = 0;
for (int i = 0; i < cities; i++) {
if (!visited[i]) {
dfs(isConnected, visited, cities, i);
provinces++;
}
}
return provinces;
}
};
My own ( iteration ):
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
// The adjacency matrix of an undirected graph is known , Find the number of connected components in the graph
int size = isConnected.size(), ans = 0, city;
stack<int> tmp;
vector<bool> visited(size, false);
for(int n = 0; n < size; n++){
// The city has not been divided into provinces
if(visited[n] == false){
++ans;
tmp.push(n);
while(!tmp.empty()){
city = tmp.top();
tmp.pop();
if(visited[city] == true) continue;
visited[city] = true; // Division of provinces
for(int i = 0; i < size; i++)
if(isConnected[city][i] == 1) tmp.push(i);
}
}
}
return ans;
}
};
Complexity analysis
Time complexity : O ( n 2 ) O(n^2) O(n2), among n n n It's the number of cities . Need to traverse the matrix isConnected \textit{isConnected} isConnected Every element in .
Spatial complexity : O ( n ) O(n) O(n), among n n n It's the number of cities . You need to use an array visited \textit{visited} visited Record whether each city has been visited , The length of the array is n n n, The depth of the recursive call stack will not exceed n n n.
Method 2 :BFS
Ideas
You can also get the total number of provinces by breadth first search . For every city , If the city has not been visited , Then start breadth first search from the city , Until all cities in the same connected component are visited , You can get a province .
Code implementation
Leetcode Official explanation :
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int cities = isConnected.size();
vector<int> visited(cities);
int provinces = 0;
queue<int> Q;
for (int i = 0; i < cities; i++) {
if (!visited[i]) {
Q.push(i);
while (!Q.empty()) {
int j = Q.front(); Q.pop();
visited[j] = 1;
for (int k = 0; k < cities; k++) {
if (isConnected[j][k] == 1 && !visited[k]) {
Q.push(k);
}
}
}
provinces++;
}
}
return provinces;
}
};
My own ( Iterative writing ):
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
// The adjacency matrix of an undirected graph is known , Find the number of connected components in the graph
int size = isConnected.size(), ans = 0, city;
queue<int> tmp;
vector<bool> visited(size, false);
for(int n = 0; n < size; n++){
// The city has not been divided into provinces
if(visited[n] == false){
++ans;
tmp.push(n);
while(!tmp.empty()){
city = tmp.front();
tmp.pop();
if(visited[city] == true) continue;
visited[city] = true; // Division of provinces
for(int i = 0; i < size; i++)
if(isConnected[city][i] == 1) tmp.push(i);
}
}
}
return ans;
}
};
Complexity analysis
Time complexity : O ( n 2 ) O(n^2) O(n2), among n n n It's the number of cities . Need to traverse the matrix isConnected \textit{isConnected} isConnected Every element in .
Spatial complexity : O ( n ) O(n) O(n), among n n n It's the number of cities . You need to use an array visited \textit{visited} visited Record whether each city has been visited , The length of the array is n n n, The number of elements in the queue used by breadth first search will not exceed n n n.
Method 3 : Union checking set
Ideas
Another way to calculate the number of connected components is to use union search set . At the beginning , Each city belongs to a different connectivity component . ergodic matrix isConnected \textit{isConnected} isConnected, If there is a connection between two cities , Then they belong to the same connected component , Merge them .
ergodic matrix isConnected \textit{isConnected} isConnected After all the elements of , Calculate the total number of connected components , That is the total number of provinces .
Code implementation
Leetcode Official explanation :
class Solution {
public:
int Find(vector<int>& parent, int index) {
if (parent[index] != index) {
parent[index] = Find(parent, parent[index]);
}
return parent[index];
}
void Union(vector<int>& parent, int index1, int index2) {
parent[Find(parent, index1)] = Find(parent, index2);
}
int findCircleNum(vector<vector<int>>& isConnected) {
int cities = isConnected.size();
vector<int> parent(cities);
for (int i = 0; i < cities; i++) {
parent[i] = i;
}
for (int i = 0; i < cities; i++) {
for (int j = i + 1; j < cities; j++) {
if (isConnected[i][j] == 1) {
Union(parent, i, j);
}
}
}
int provinces = 0;
for (int i = 0; i < cities; i++) {
if (parent[i] == i) {
provinces++;
}
}
return provinces;
}
};
My own :
class Solution {
int Find(vector<int>& citys, int city){
if(citys[city] == city) return city;
else return citys[city] = Find(citys, citys[city]);
}
void Union(vector<int>& citys, int city1, int city2){
citys[Find(citys, city2)] = Find(citys, city1); // Connect the two sets
}
public:
int findCircleNum(vector<vector<int>>& isConnected) {
// The adjacency matrix of an undirected graph is known , Find the number of connected components in the graph
int size = isConnected.size(), ans = 0, city, root1, root2;
vector<int> citys;
// Create and query an array
for(int n = 0; n < size; n++)
citys.push_back(n);
for(int n = 0; n < size; n++){
for(int i = 0; i < size; i++){
if(isConnected[n][i] == 1)
Union(citys, n, i);
}
}
for(int n = 0; n < size; n++)
if(citys[n] == n) ans++;
return ans;
}
};
Complexity analysis
Time complexity : O ( n 2 log n ) O(n^2 \log n) O(n2logn), among n n n It's the number of cities . Need to traverse the matrix isConnected \textit{isConnected} isConnected All elements in , The time complexity is O ( n 2 ) O(n^2) O(n2), If you encounter a connection , You need to do 2 2 2 Find and maximum 1 1 1 The merger , A total of 2 n 2 2n^2 2n2 Find and maximum n 2 n^2 n2 The merger , So the total time complexity is O ( 2 n 2 log n 2 ) = O ( n 2 log n ) O(2n^2 \log n^2)=O(n^2 \log n) O(2n2logn2)=O(n2logn). The join set here uses path compression , However, rank merging is not used , The worst-case time complexity is O ( n 2 log n ) O(n^2 \log n) O(n2logn), The average time complexity is still O ( n 2 α ( n ) ) O(n^2 \alpha (n)) O(n2α(n)), among α \alpha α Is the inverse of the Ackerman function , α ( n ) \alpha (n) α(n) It can be considered a very small constant .
Spatial complexity : O ( n ) O(n) O(n), among n n n It's the number of cities . You need to use an array parent \textit{parent} parent Record the ancestors of the connected components to which each city belongs .
边栏推荐
- Advanced learning of MySQL -- basics -- basic operation of transactions
- Leetcode(547)——省份数量
- Alexnet experiment encounters: loss Nan, train ACC 0.100, test ACC 0.100
- 基於GO語言實現的X.509證書
- Mujoco second order simple pendulum modeling and control
- Basic information of mujoco
- St table
- Value Function Approximation
- Leecode brush questions record sword finger offer 11 Rotate the minimum number of the array
- How engineers treat open source -- the heartfelt words of an old engineer
猜你喜欢
Distributed cache
JS+SVG爱心扩散动画js特效
Data analysis course notes (V) common statistical methods, data and spelling, index and composite index
Stm32f407 ------- SPI communication
智能运维应用之道,告别企业数字化转型危机
48 page digital government smart government all in one solution
Five different code similarity detection and the development trend of code similarity detection
【vulnhub】presidential1
Attention SLAM:一種從人類注意中學習的視覺單目SLAM
stm32F407-------DAC数模转换
随机推荐
QT tutorial: creating the first QT program
Devops can help reduce technology debt in ten ways
AI super clear repair resurfaces the light in Huang Jiaju's eyes, Lecun boss's "deep learning" course survival report, beautiful paintings only need one line of code, AI's latest paper | showmeai info
How can computers ensure data security in the quantum era? The United States announced four alternative encryption algorithms
Three sentences to briefly introduce subnet mask
@TableId can‘t more than one in Class: “com.example.CloseContactSearcher.entity.Activity“.
Why should a complete knapsack be traversed in sequence? Briefly explain
接口(接口相关含义,区别抽象类,接口回调)
37頁數字鄉村振興智慧農業整體規劃建設方案
Policy Gradient Methods
Sword finger offer 26 Substructure of tree
If the college entrance examination goes well, I'm already graying out at the construction site at the moment
What is web penetration testing_ Infiltration practice
509 certificat basé sur Go
Operation test of function test basis
Geo data mining (III) enrichment analysis of go and KEGG using David database
Slam d'attention: un slam visuel monoculaire appris de l'attention humaine
Amazon MemoryDB for Redis 和 Amazon ElastiCache for Redis 的内存优化
Clipboard management tool paste Chinese version
Quaternion attitude calculation of madgwick