C++刷leetcode(323. 无向图中连通分量的数目)【并查集】
本帖最后由 糖逗 于 2020-5-8 17:35 编辑题目描述：
给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。
示例 1:
输入: n = 5 和 edges = [, , ]
0 3
| |
1 --- 2 4
输出: 2
示例 2:
输入: n = 5 和 edges = [, , , ]
0 4
| |
1 --- 2 --- 3
输出: 1
注意:
你可以假设在 edges 中不会出现重复的边。而且由于所以的边都是无向边， 与 相同，所以它们不会同时在 edges 中出现。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-connected-components-in-an-undirected-graph
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include <iostream>
#include <vector>
using namespace std;
vector<int> parent;
vector<int> len;
int count;
//寻找根节点
int FindRoot(int x){
while(parent != x){
parent = parent];
x = parent;
}
return x;
}
void Union(int x, int y){
int rootX = FindRoot(x);
int rootY = FindRoot(y);
if(rootX == rootY) return;
if(len >= len){
parent = rootX;
len += len;
}
else{
parent = rootY;
len += len;
}
count--;
}
int solution(int n, vector<vector<int> >& edge){
count = n;
//初始化parent
for(int i = 0; i < n; i++){
parent.push_back(i);
len.push_back(1);
}
for(auto e : edge){
Union(e, e);
}
return count;
}
int main(void){
int n;
cout << "send the total number of nodes" << endl;
cin >> n;
cin.clear();
cout << "send the row for the input vector" << endl;
int row;
cin >> row;
cin.clear();
vector<vector<int> > input;
input.resize(row);
int number;
for(int i = 0; i < row; i++){
for(int j = 0; j < 2; j++){
cin >> number;
input.push_back(number);
}
}
int res = solution(n, input);
cout << res << endl;
return 0;
}
注意事项：
1.并查集，参考视频：https://www.bilibili.com/video/BV1Jx411b7F3?from=search&seid=4500170862695587041
2.参考代码：https://leetcode-cn.com/problems/number-of-connected-components-in-an-undirected-graph/solution/c-union-findjie-fa-by-kingpray/
3.并查集是常用的判断图中是否有环的数据结构 都跟你说了弄成悬赏贴（跟zltzlt的Python每日一题那样的，不过鱼币不用太多）
页:
[1]