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

糖逗

题目描述：

给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。

示例 1:

输入: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]]

     0          3
     |          |
     1 --- 2    4 

输出: 2
示例 2:

输入: n = 5 和 edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

     0           4
     |           |
     1 --- 2 --- 3

输出:  1
注意:
你可以假设在 edges 中不会出现重复的边。而且由于所以的边都是无向边，[0, 1] 与 [1, 0]  相同，所以它们不会同时在 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] != x){
                parent[x] = parent[parent[x]];
                x = parent[x];
        }
        return x;
}


void Union(int x, int y){
        int rootX = FindRoot(x);
        int rootY = FindRoot(y);
        if(rootX == rootY) return;
        if(len[rootX] >= len[rootY]){
                parent[rootY] = rootX;
                len[rootX] += len[rootY];
        }
        else{
                parent[rootX] = rootY;
                len[rootY] += len[rootX];
        }
        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[0], e[1]);
        }
        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[i].push_back(number);
                } 
        }
        
        int res = solution(n, input);
        cout << res << endl;
        
        return 0;
} 

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

乘号

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