Link to Question

MEDIUM

Count the Number of Complete Components

You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are also given a 2D integer array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi.

Return the number of complete connected components of the graph.

A complete component is a connected component such that every pair of nodes is connected by an edge.

Example

Input:

n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]

Output:

3

Explanation: There are 3 complete components: - Nodes 0, 1, 2 form a complete component (each pair is connected). - Nodes 3, 4 form a complete component. - Node 5 forms a complete component by itself.

---

Constraints

• 1 ≤ n ≤ 50
• 0 ≤ edges.length ≤ n * (n - 1) / 2
• edges[i].length == 2
• 0 ≤ ai, bi < n
• ai != bi
• There are no repeated edges.

---

Solution: DFS

• Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges.
• Space Complexity: O(n + m), where n is the number of nodes and m is the number of edges.

C++

class Solution {
public:
    void dfs(int i, int& count, int& edges, unordered_map<int, vector<int>>& m, vector<int>& v) {
        if (v[i]) return;
        count++;
        v[i] = 1;
        if (m.count(i)) {
            for (auto c : m[i]) {
                edges++;
                dfs(c, count, edges, m, v);
            }
        }
    }

    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        unordered_map<int, vector<int>> m;
        for(auto& e : edges) {
            m[e[0]].push_back(e[1]);
            m[e[1]].push_back(e[0]);
        }
        vector<int> visited(n, 0);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int count = 0, edges = 0;
            if (visited[i] == 0) {
                dfs(i, count, edges, m, visited);
                ans += (edges == (count-1)*count);
            }
        }
        return ans;
    }
};