​LeetCode刷题实战323：无向图中连通分量的数目

class Solution {
public:
    //找每一个顶点的老大
    int find_father(vector<int> &f, int i){
        while(i!=f[i]){
            i=f[i];
        } 
        return i;
    }
 
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<int>f(n);
        //将每一个顶点单独分成一组
        for(int i=0; i<n; ++i){
            f[i]=i;
        }
        //进行同一组的顶点的合并
        for(auto x:edges){
            int p=find_father(f, x[0]);
            int q=find_father(f, x[1]);
            if(p==q) continue;
            else f[p]=q;
        } 
        //找一共有多少个不同的老大
        unordered_set<int>s;
        for(int i=0; i<f.size(); ++i){
            s.insert(find_father(f, i));
        }
        return s.size();
    }
};