统计完全连通分量的数量 图解题解

这道题到底在问什么

输入

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

最优解：一步一步想明白

1. 3记牢这一句:一块连通分量,顶点数是 x、度数和是 y,只要 x 乘以 x 减 1 等于 y,它就是完全分量。用度数和来判,省得单独去数边、也不怕重复。下面从顶点 0 开始,一块一块地走。
2. 4概览:三块待判定这是我们要处理的图。一眼看去,顶点自然分成三块:左边 0、1、2 三个点两两连着,像个三角形;中间 3、4、5,3 分别连到 4 和 5,可 4 和 5 之间是断开的;右边 6 是个光杆,一条边都没有。这三块就是三个连通分量,接下来逐块检验它们完不完全。
3. 5判据:两两相连先把完全的判据说清。一块有 x 个顶点,要让它们两两之间都直接有边,一共需要 x 乘以 x 减 1 再除以 2 条边。1 个点不需要边,天生完全;2 个点要 1 条边;3 个点要 3 条边,也就是凑成一个三角形。等会儿每走完一块,就拿它实际的边数和这个应有的边数比一比。
4. 6技巧:y = 度数和这里有个省事的巧劲。与其小心翼翼地数边,不如把块里每个顶点的度数加起来,记成 y。因为每条边连着两个端点,会在两个端点的度数里各被算一次,所以 y 刚好是边数的 2 倍。这么一来,完全的条件从「边数等于 x 乘 x 减 1 除以 2」直接变成「y 等于 x 乘 x 减 1」,遍历时顺手就把 y 累出来了。
5. 7外层:找起点整体框架是这样:外层用 i 从 0 扫到 6,一旦碰到一个还没被访问过的顶点,就以它为起点发起一次深度优先遍历,把它所在的一整块分量走遍,同时把这块的 x 和 y 累出来。走过的点随手标记已访问,外层就不会重复进同一块。下面开始扫。
6. 8分量一开工外层从 0 开始,0 还没访问过,就以它为起点发起 DFS。开一个计数:顶点数 x 先记 1,度数和 y 先把 0 的度数加进去。0 连着 1 和 2 两条边,度数是 2,所以 y 现在是 2。0 就是这块分量的第一个顶点。
7. 9当前:顶点 0站在 0,把它标成正在处理。看它的邻接表,邻居是 1 和 2,都还没访问。深度优先的规矩是先认准一个邻居钻到底,再回头处理另一个。按建图的顺序,先走去 1。两条从 0 出发的边先点亮,表示待会儿都要走。
8. 10进入:顶点 1顺着边 0-1 走到 1,把它收进这块分量。x 从 1 加到 2。1 也连着两条边,连到 0 和 2,度数是 2,把它加进 y,y 从 2 变成 4。1 这个点先标成刚够到的蓝色,马上轮到处理它。
9. 11当前:顶点 1轮到处理 1。它的邻居是 0 和 2,0 刚才已经访问过了,跳过,只剩 2 还没走。那就沿着边 1-2 继续往下钻。深度优先就是这样一条路走到底,把能连的都串起来。
10. 12进入:顶点 2走到 2,收进分量,x 加到 3。2 连着 0 和 1 两条边,度数是 2,加进 y,y 从 4 变成 6。到这儿这块分量的三个顶点 0、1、2 都收齐了,x 是 3,y 是 6。
11. 13当前:顶点 2处理 2 的时候,它的邻居 0 和 1 都访问过了,这块就到头了。注意看,除了走过的 0-1、1-2,0 和 2 之间同样有一条边。也就是说 0、1、2 这三对顶点,每一对都直接连着。这一点度数和已经替我们记下了:y 等于 6。
12. 14结算:完全这块分量走完,x 是 3、y 是 6。套判据:x 乘以 x 减 1 等于 3 乘 2 等于 6,正好等于 y。等式成立,0、1、2 是一个完全分量。把三个顶点整块涂绿,完全分量数从 0 加到 1。
13. 15分量二开工外层继续往后扫,1、2 都访问过了,扫到 3,它还没访问,又发起一次 DFS。计数重新开张:x 记 1。3 连着 4 和 5 两条边,度数是 2,y 先记 2。开始走这块新的分量。
14. 16当前:顶点 3站在 3,看它的邻居,是 4 和 5,都没访问。按顺序先钻去 4。两条从 3 出发的边先点亮。你先记着一个悬念:3 分别连着 4 和 5,可 4 跟 5 彼此之间有没有边,得走过去才知道。
15. 17进入:顶点 4顺着边 3-4 到 4,收进分量,x 加到 2。可这次不一样:4 只连着 3 这一条边,度数是 1,加进 y 只让 y 从 2 变成 3。度数和涨得慢,已经在暗示这块的边不太够了。
16. 18当前:顶点 4处理 4,它的邻居只有一个 3,还是已经访问过的。这条路到头了,退回 3。你看,4 这个点是个叶子,除了拴在 3 上,和别人没有任何联系。回到 3 去走它另一个还没走的邻居 5。
17. 19进入:顶点 5回到 3,沿边 3-5 走到 5,收进分量,x 加到 3。5 也一样,只连着 3 这一条边,度数是 1,y 从 3 变成 4。三个顶点 3、4、5 都收齐了,可 x 是 3、y 只有 4。
18. 20发现:缺一条边把这块看清楚:3 像个中心,分别拉着 4 和 5,可是 4 和 5 之间空着,没有边。3 个顶点要想两两相连得有 3 条边,凑成三角形,这里只有 3-4、3-5 两条。缺了 4-5 那条,这块就不是完全分量。
19. 21结算:不完全算一下:x 乘以 x 减 1 是 3 乘 2 等于 6,可 y 只有 4,等式不成立。所以 3、4、5 这块不是完全分量,不计数。把它们恢复成常态的灰色,完全分量数还是 1,一个没加。度数和差在哪儿一目了然:少一条边,y 就少 2。
20. 22分量三开工外层扫到最后一个点 6,它还没访问,发起 DFS。6 是个孤立点,一条边都没有。x 记 1,它的度数是 0,y 就是 0。这块分量只有它自己一个顶点。
21. 23当前:顶点 6处理 6,它的邻接表是空的,没有邻居可走,这块分量就它一个点,直接结束。x 是 1,y 是 0。别小看这种单点分量,它其实是完全分量里最特殊的一种。
22. 24结算:完全套判据:x 乘以 x 减 1 是 1 乘 0 等于 0,y 也是 0,等式成立。所以单个孤立点 6 也是一个完全分量,因为它里面根本没有「两个顶点」需要相连,判据自动满足。把 6 涂绿,完全分量数从 1 加到 2。
23. 25答案 = 2三块分量全部查完。0、1、2 三角形每对都连,完全,绿的;6 孤立点没有任何一对要连,也算完全,绿的;3、4、5 缺了 4-5 那条边,不完全,灰的。数一数绿的分量,一共 2 个,这就是答案。判定自始至终只有一句话:x 乘以 x 减 1 等不等于度数和 y。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
        def dfs(i: int) -> (int, int):
            vis[i] = True
            x, y = 1, len(g[i])
            for j in g[i]:
                if not vis[j]:
                    a, b = dfs(j)
                    x += a
                    y += b
            return x, y

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        vis = [False] * n
        ans = 0
        for i in range(n):
            if not vis[i]:
                a, b = dfs(i)
                ans += a * (a - 1) == b
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n);
        bool vis[n];
        memset(vis, false, sizeof(vis));
        for (auto& e : edges) {
            int a = e[0], b = e[1];
            g[a].push_back(b);
            g[b].push_back(a);
        }
        function<pair<int, int>(int)> dfs = [&](int i) -> pair<int, int> {
            vis[i] = true;
            int x = 1, y = g[i].size();
            for (int j : g[i]) {
                if (!vis[j]) {
                    auto [a, b] = dfs(j);
                    x += a;
                    y += b;
                }
            }
            return make_pair(x, y);
        };
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (!vis[i]) {
                auto [a, b] = dfs(i);
                if (a * (a - 1) == b) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    private List<Integer>[] g;
    private boolean[] vis;

    public int countCompleteComponents(int n, int[][] edges) {
        g = new List[n];
        vis = new boolean[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] e : edges) {
            int a = e[0], b = e[1];
            g[a].add(b);
            g[b].add(a);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (!vis[i]) {
                int[] t = dfs(i);
                if (t[0] * (t[0] - 1) == t[1]) {
                    ++ans;
                }
            }
        }
        return ans;
    }

    private int[] dfs(int i) {
        vis[i] = true;
        int x = 1, y = g[i].size();
        for (int j : g[i]) {
            if (!vis[j]) {
                int[] t = dfs(j);
                x += t[0];
                y += t[1];
            }
        }
        return new int[] {x, y};
    }
}

复杂度

面试官可能追问