?LeetCode刷題實戰(zhàn)323：無向圖中連通分量的數(shù)目

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;
        }
        //進(jìn)行同一組的頂點的合并
        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();
    }
};