C++ union bound O(mn) solution


  • 0
    M
    class Solution {
    public:
        int countComponents(int n, vector<pair<int, int>>& edges) {
            vector<int> id(n);
            iota(id.begin(),id.end(),0);
            for(int i=0;i<edges.size();i++){
                if(id[edges[i].first] != id[edges[i].second]){
                    int temp = id[edges[i].first];
                    for(int j=0;j<n;j++){
                        if(id[j] == temp){
                            id[j] = id[edges[i].second];
                        }
                    }
                }
            }
            unordered_map<int, int> m;
            int count = 0;
            for(int i=0;i<n;i++){
                if(m.find(id[i]) == m.end()){
                    m[id[i]]++;
                    count++;
                }
                else{
                    m[id[i]]++;
                }
            }
            return m.size();
        }
    };

Log in to reply
 

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