C++刷leetcode(323. 无向图中连通分量的数目)【并查集】

糖逗

题目描述：

1. 给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。
   
2. 
   
3. 示例 1:
   
4. 
   
5. 输入: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]]
   
6. 
   
7.      0          3
   
8.      |          |
   
9.      1 --- 2    4
   
10. 
    
11. 输出: 2
    
12. 示例 2:
    
13. 
    
14. 输入: n = 5 和 edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
    
15. 
    
16.      0           4
    
17.      |           |
    
18.      1 --- 2 --- 3
    
19. 
    
20. 输出:  1
    
21. 注意:
    
22. 你可以假设在 edges 中不会出现重复的边。而且由于所以的边都是无向边，[0, 1] 与 [1, 0]  相同，所以它们不会同时在 edges 中出现。
    
23. 
    
24. 来源：力扣（LeetCode）
    
25. 链接：https://leetcode-cn.com/problems/number-of-connected-components-in-an-undirected-graph
    
26. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. using namespace std;
   
5. 
   
6. vector<int> parent;
   
7. vector<int> len;
   
8. int count;
   
9. 
   
10. //寻找根节点
    
11. int FindRoot(int x){
    
12.         while(parent[x] != x){
    
13.                 parent[x] = parent[parent[x]];
    
14.                 x = parent[x];
    
15.         }
    
16.         return x;
    
17. }
    
18. 
    
19. 
    
20. void Union(int x, int y){
    
21.         int rootX = FindRoot(x);
    
22.         int rootY = FindRoot(y);
    
23.         if(rootX == rootY) return;
    
24.         if(len[rootX] >= len[rootY]){
    
25.                 parent[rootY] = rootX;
    
26.                 len[rootX] += len[rootY];
    
27.         }
    
28.         else{
    
29.                 parent[rootX] = rootY;
    
30.                 len[rootY] += len[rootX];
    
31.         }
    
32.         count--;
    
33. }
    
34. 
    
35. 
    
36. int solution(int n, vector<vector<int> >& edge){
    
37.         count = n;
    
38.         //初始化parent
    
39.         for(int i = 0; i < n; i++){
    
40.                 parent.push_back(i);
    
41.                 len.push_back(1);
    
42.         }
    
43.         for(auto e : edge){
    
44.                 Union(e[0], e[1]);
    
45.         }
    
46.         return count;
    
47. }
    
48. 
    
49. 
    
50. 
    
51. int main(void){
    
52.         int n;
    
53.         cout << "send the total number of nodes" << endl;
    
54.         cin >> n;
    
55.         cin.clear();
    
56.         cout << "send the row for the input vector" << endl;
    
57.         int row;
    
58.         cin >> row;
    
59.         cin.clear();
    
60.         vector<vector<int> > input;
    
61.         input.resize(row);
    
62.         int number;
    
63.         for(int i = 0; i < row; i++){
    
64.                 for(int j = 0; j < 2; j++){
    
65.                         cin >> number;
    
66.                         input[i].push_back(number);
    
67.                 }
    
68.         }
    
69.        
    
70.         int res = solution(n, input);
    
71.         cout << res << endl;
    
72.        
    
73.         return 0;
    
74. }

复制代码

注意事项：
1.并查集，参考视频：https://www.bilibili.com/video/B ... 4500170862695587041
2.参考代码：https://leetcode-cn.com/problems ... jie-fa-by-kingpray/
3.并查集是常用的判断图中是否有环的数据结构

乘号

都跟你说了弄成悬赏贴（跟zltzlt的Python每日一题那样的，不过鱼币不用太多）