题目描述

给你一个整数 n。现有一个包含 n 个顶点的 无向 图，顶点按从 0 到 n - 1 编号。给你一个二维整数数组 edges 其中 edges[i] = [a_i, b_i] 表示顶点 a_i 和 b_i 之间存在一条 无向 边。

返回图中 完全连通分量 的数量。

如果在子图中任意两个顶点之间都存在路径，并且子图中没有任何一个顶点与子图外部的顶点共享边，则称其为 连通分量。

如果连通分量中每对节点之间都存在一条边，则称其为 完全连通分量。

样例

输入：n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]
输出：3
解释：如上图所示，可以看到此图所有分量都是完全连通分量。

输入：n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]
输出：1
解释：包含节点 0、1 和 2 的分量是完全连通分量，因为每对节点之间都存在一条边。
包含节点 3、4 和 5 的分量不是完全连通分量，因为节点 4 和 5 之间不存在边。
因此，在图中完全连接分量的数量是 1 。

限制

• 1 <= n <= 50
• 0 <= edges.length <= n * (n - 1) / 2
• edges[i].length == 2
• 0 <= a_i, b_i <= n - 1
• a_i != b_i
• 不存在重复的边。

算法

(宽度优先遍历) $O(n + m)$

1. 宽度优先遍历求出每个连通分量，统计连通分量的点数和边数是否构成完全图。

时间复杂度

• 每个节点和边被遍历一次，故时间复杂度为 $O(n + m)$。

空间复杂度

• 需要 $O(n + m)$ 的额外空间存储宽搜的队列和访问数组。

C++ 代码

class Solution {
private:
    vector<bool> seen;
    vector<vector<int>> graph;

    int check(int st, int n) {
        seen[st] = true;
        queue<int> q;
        q.push(st);

        int sz = 0, tot = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();

            ++sz;
            tot += graph[u].size();

            for (int v : graph[u])
                if (!seen[v]) {
                    seen[v] = true;
                    q.push(v);
                }
        }

        return tot == sz * (sz - 1);
    }

public:
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        graph.resize(n);
        for (const auto &e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }

        seen.resize(n, false);

        int ans = 0;
        for (int i = 0; i < n; i++)
            if (!seen[i])
                ans += check(i, n);

        return ans;
    }
};