Count the Number of Complete Components

Leetcode Problem:

• Count the Number of Complete Components

Summary

• This is a problem about finding the number of complete connected components in a graph.

Approach

• The approach used in the solution code is to use a disjoint set data structure to keep track of the connected components in the graph
• The code first initializes the disjoint set data structure and then iterates over the edges in the graph
• For each edge, it checks if the two vertices are in the same connected component
• If they are not, it merges the two components by attaching the root of one component to the root of the other component
• The code also keeps track of the number of edges in each component
• Finally, it checks each component to see if it is complete by checking if the number of edges in the component is equal to the number of ways to choose two vertices from the component (i.e., n*(n-1)/2)
• If a component is not complete, it is removed from the set of components
• The final answer is the number of complete components remaining in the set.

Complexity

• O(n*m*log(n)) where n is the number of vertices and m is the number of edges in the graph.

Explanation

• The code first initializes the disjoint set data structure and the edge count array
• It then iterates over the edges in the graph and checks if the two vertices are in the same connected component
• If they are not, it merges the two components by attaching the root of one component to the root of the other component
• The code also keeps track of the number of edges in each component
• Finally, it checks each component to see if it is complete by checking if the number of edges in the component is equal to the number of ways to choose two vertices from the component (i.e., n*(n-1)/2)
• If a component is not complete, it is removed from the set of components
• The final answer is the number of complete components remaining in the set.

Solution Code:

class Solution {
public:
    int uf[51];
    int edgeCnt[51] = {0};
    int groupCnt[51] = {0};
    int disjointSet(int x){
        if (x == uf[x]) return x;
        return uf[x] = disjointSet(uf[x]);
    }
    int countCompleteComponents(int n, vector>& edges) {
        if (n == 1) return 1;
        set ans;
        for(int i = 0 ; i < n; i++){
            uf[i] = i;
            groupCnt[i] = 1;
        }
        for(int i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            if(disjointSet(a) != disjointSet(b)){
                groupCnt[disjointSet(b)] += groupCnt[disjointSet(a)];
                groupCnt[disjointSet(a)] = 0;
                edgeCnt[disjointSet(b)] += edgeCnt[disjointSet(a)];
                edgeCnt[disjointSet(b)] += 1;
                edgeCnt[disjointSet(a)] = 0;
                uf[disjointSet(a)] = disjointSet(b);
            }else{
                edgeCnt[disjointSet(b)] += 1;
            }
        }
        for(int i = 0 ; i < n; i++){
            if(ans.find(disjointSet(i)) == ans.end()){
                ans.insert(disjointSet(i));
            }
        }
        cout << "answer size: " << ans.size() << endl;
        vector removeList;
        for(auto idx : ans){
            int n = groupCnt[disjointSet(idx)];
            int e = edgeCnt[disjointSet(idx)];
            cout << n << " " << e << endl;
            if((n*(n-1)/2) != e){
                removeList.push_back(idx);
            }
        }
        for(int i = 0 ; i < removeList.size(); i++){
            ans.erase(removeList[i]);
        }
        return ans.size();
    }
};