C++ SolutionDFS and Union Find version


  • 0
    Y
    //DFS Version    
    class Solution {
        public:
            int countComponents(int n, vector<pair<int, int>>& edges) {
                int ans = 0;
                if(!n)
                    return ans;
                if(!edges.size())
                    return n;
                vector<bool> vis(n);
                unordered_map<int,unordered_set<int>> mp;
                for(int i = 0; i < edges.size(); ++ i){
                    mp[edges[i].first].insert(edges[i].second);
                    mp[edges[i].second].insert(edges[i].first);
                }
                for(int i = 0; i < n; ++ i){
                    if(!vis[i]){
                        ++ ans;
                        dfs(i, vis, mp);
                    }
                }
                return ans;
            }
            
        private:
            void dfs(int u, vector<bool> &vis, unordered_map<int,unordered_set<int>> &mp){
                vis[u] = 1;
                unordered_set<int>::iterator it = mp[u].begin();
                for(; it != mp[u].end(); ++ it){
                    int v = *it;
                    if(!vis[v]){
                        dfs(v, vis, mp);
                    }
                }
            }
            
        };
    
    
    
    
    //Union Find Version
    class Solution {
    public:
        int countComponents(int n, vector<pair<int, int>>& edges) {
            int ans = 0;
            if(!n)
                return ans;
            if(!edges.size())
                return n;
            fa.resize(n);
            for(int i = 0; i < n; ++ i)
                fa[i] = -1;
            
            ans = n;
            for(int i = 0; i < edges.size(); ++ i){
                if(find(edges[i].first) != find(edges[i].second)){
                    -- ans;
                    unionedge(edges[i].first, edges[i].second);
                }
            }
            
            return ans;
        }
        
        int find(int u){
            int s = u;
            for(; fa[s] >= 0; s = fa[s]) ;
            while(u != s){
                int tmp = fa[u];
                fa[u] = s;
                u = tmp;
            }
            return s;
        }
        
        void unionedge(int a, int b){
            int f1 = find(a), f2 = find(b);
            int sumf = fa[f1] + fa[f2];
            if(fa[f1] <= fa[f2]){
                fa[f2] = f1;
                fa[f1] = sumf;
            }else{
                fa[f1] = f2;
                fa[f2] = sumf;
            }
        }
        
    private:
    vector<int> fa;
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.