Succinct C++ solution beats 100%


  • 0
    W
    int countComponents(int n, vector<pair<int, int>>& edges) {
        if (n == 0) return 0;
        vector<int> heads(n, -1);
        
        for (auto e : edges) {
            if (heads[e.first] == -1 && heads[e.second] == -1) {
                heads[e.first] = e.first;
                heads[e.second] = e.first;
            } else if (heads[e.first] != -1 && heads[e.second] == -1) {
                heads[e.second] = heads[e.first];
            } else if (heads[e.first] == -1 && heads[e.second] != -1) {
                heads[e.first] = heads[e.second];
            } else {
                int tmp = heads[e.second];
                int val = heads[e.first];
                for (auto &h : heads) {
                    if (h == tmp) {
                        h = val;
                    }
                }
            }
        }
        
        int count=1;
        sort(heads.begin(), heads.end());
        for (int i=1; i<heads.size(); i++) {
            if (heads[i] != heads[i-1] || heads[i] == -1) {
                count++;
            }
        }
        
        
        return count;
    }

Log in to reply
 

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