2685: Count-the-Number-of-Complete-Components
Medium

This solution hinges on Breadth-first Search.

Realise that, to verify if a component is connected or not, we can:

Then, we check all the connected nodes; for the node to be a part of a completed connected component:

If the nodes is not a part of a completed connected component, we can simply run DFS until we search the entire component and mark all its nodes as seen.

Code:

class Solution {
public:
    bool bfs(int& current, int parent_size, vector<vector<int>> &adjacencyMatrix, vector<int> &seen) {
        bool complete = true;
        if (adjacencyMatrix[current].size() != parent_size) complete = false;
        
        seen[current] = 1;
        for (int child : adjacencyMatrix[current]) {
            if (seen[child] == 1) continue;

            complete = false;
            bfs(child, parent_size, adjacencyMatrix, seen);
        }

        if (complete == true) {
            return true;
        } else {
            return false;
        }
    }
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        vector<int> seen(n, 0);
        vector<vector<int>> adjacencyMatrix(n);

        for (int i = 0; i < edges.size(); ++i) {
            adjacencyMatrix[edges[i][0]].push_back(edges[i][1]);
            adjacencyMatrix[edges[i][1]].push_back(edges[i][0]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (seen[i] == 1) continue;

            seen[i] = 1;

            bool complete = true;
            for (int child : adjacencyMatrix[i]) {
                seen[child] = 1;
            }
            for (int child : adjacencyMatrix[i]) {
                if (!bfs(child, (int)adjacencyMatrix[i].size(), adjacencyMatrix, seen)) {
                    complete = false;
                }
            }
            if (complete == true) {
                ++ans;
            }
        }
        return ans;
    }
};

Complexity: