E. Cyclic Components - 题解

比赛与标签

比赛: Codeforces Round 479 (Div. 3) 标签: dfs and similar, dsu, graphs 难度: *1500

题目大意喵~

主人 sama，下午好呀！今天我们来解决一个关于图图的有趣问题呐~ ฅ(●'ω`●)ฅ

题目会给我们一个无向图，它有很多个点（vertices）和边（edges）。我们的任务是，找出这个图里有多少个“连通分量”是完美的“环”。

那么，什么样的连通分量才算是一个完美的“环”呢？

1. 首先，它自己内部必须是连通的，也就是说，这个分量里的任意两个点之间都有路径可以到达。
2. 其次，这个连通分量里的所有点，都可以排成一个圈圈，比如 v1, v2, ..., vk，然后 v1 和 v2 有边，v2 和 v3 有边，...，最后 vk 和 v1 也有边，形成一个闭合的路径。
3. 最最重要的一点是，这个分量里不能有任何多余的边！也就是说，除了形成这个圈圈所必需的边之外，再也没有其他的边了。
4. 哦对了，一个合格的环至少要有3个顶点哦！

就像下面这张图里，[7,10,16] 和 [5,11,9,15] 就是两个完美的环形连通分量。我们的目标就是数出这样的环有几个！

解题思路分析喵~

要找到这些完美的环，我们首先得想一想，一个完美的环形连通分量有什么独特的性质呢？喵？

主人请想一下，如果一群小猫咪手拉手围成一个圈，每只小猫咪是不是都只拉着左右两边的小伙伴呢？不多也不少，正好是两只！(＾• ω •＾)

对啦！这就是关键！在一个完美的环里，每一个顶点的度数（degree，也就是连接到这个点的边的数量）都必须恰好是 2！

有了这个超级重要的发现，我们的解题思路就变得非常清晰了呢：

1. 遍历所有顶点：我们可以从顶点1到顶点n，一个一个地检查过去。
2. 寻找连通分量：如果当前检查到的顶点 i 还没有被访问过，那就说明我们发现了一个新的、未探索的连通分量！耶！我们可以从这个点 i 出发，使用 广度优先搜索（BFS） 或者 深度优先搜索（DFS） 来找到这个连通分量里的所有顶点。
3. 收集分量信息：在用BFS/DFS遍历的时候，我们可以把当前连通分量的所有顶点都收集到一个列表里，同时把它们都标记为“已访问”，这样就不会重复处理啦。
4. 进行神圣的检查：当一个连通分量的所有顶点都找到后，我们就来检查它是不是一个完美的环。
   • 首先，成员数量不能少于3个。
   • 然后，我们遍历刚才收集到的顶点列表，检查列表里的每一个顶点，它的度数是不是都等于2。
5. 计数：如果这个连通分量通过了所有的检查（成员数>=3，且所有成员度数都为2），那么恭喜！我们找到了一个完美的环形分量！我们的计数器就可以 +1 啦！
6. 重复：继续向后检查，直到所有的顶点都被访问过为止。

这个方法可以确保我们不重不漏地检查完图中的每一个连通分量，并准确地判断出哪些是环。是不是很简单呢，的说！

代码实现魔法时间！

下面就是实现这个思路的魔法代码啦！我已经为主人加上了详细的注释，方便理解每一句都在做什么哦~

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    // 加速输入输出，让程序跑得像猫一样快喵~
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m; // n 是顶点数，m 是边数
    cin >> n >> m;

    // 用邻接表来存图图，方便又快捷喵~
    vector<vector<int>> graph(n + 1);
    // deg数组用来记录每个点点的“朋友”数量（度数）
    vector<int> deg(n + 1, 0);
    // visited数组防止我们重复访问同一个连通块
    vector<bool> visited(n + 1, false);

    // 读取所有的边，并构建图和计算度数
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }

    int cycleCount = 0; // 用来计数的宝箱！

    // 遍历所有顶点，寻找未被发现的连通分量
    for (int i = 1; i <= n; i++) {
        // 如果这个点已经被访问过，就说明它属于之前处理过的某个分量，直接跳过~
        if (visited[i]) continue;

        // 发现新大陆！开始BFS探索这个连通分量
        queue<int> q;
        q.push(i);
        visited[i] = true;
        vector<int> comp; // 用来存放当前连通分量的所有顶点

        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            comp.push_back(cur); // 将当前顶点加入分量列表

            // 探索当前顶点的所有邻居
            for (int neighbor : graph[cur]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true; // 标记为已访问
                    q.push(neighbor);       // 加入队列，等待探索
                }
            }
        }

        // BFS结束，我们已经找到了完整的一个连通分量
        // 首先，一个环至少要有3个顶点，太小了可不行哦
        if (comp.size() < 3) continue;

        // 检查这个连通块是不是一个完美的环环
        bool isCycle = true;
        for (int v : comp) {
            // 只要有一个点的度数不是2，它就不是一个完美的环了，呜呜
            if (deg[v] != 2) {
                isCycle = false;
                break;
            }
        }

        // 如果isCycle还是true，说明所有检查都通过了！
        if (isCycle) {
            cycleCount++; // 找到了一个环，计数器+1！
        }
    }

    cout << cycleCount << endl; // 输出最终找到的环的数量

    return 0;
}

复杂度分析

• 时间复杂度: O(N + M) 的说。

  • 我们需要 O(M) 的时间来读取所有边并构建邻接表和度数数组。
  • 之后的主循环会遍历所有顶点。由于有 visited 数组的保护，每个顶点和每条边在所有的BFS过程中只会被访问一次。所以，所有BFS的总时间复杂度是 O(N + M)。
  • 因此，总的时间复杂度就是 O(N + M)，非常高效！每个点点和每条边边我们都只会摸一遍，真棒！

• 空间复杂度: O(N + M) 的说。

  • 邻接表 graph 需要 O(N + M) 的空间来存储图的结构。
  • deg 和 visited 数组都需要 O(N) 的空间。
  • 在BFS过程中，队列 q 和存储分量的 comp 向量在最坏的情况下（整个图是一个连通分量）也需要 O(N) 的空间。
  • 所以，总的空间复杂度由邻接表主导，为 O(N + M) 呐~

知识点与总结喵

这道题真是对图论基础的一次绝佳练习呢！让本喵来总结一下我们学到了什么吧：

1. 核心思想转换：最关键的一步，是将一个抽象的、几何上的概念（“这是一个环”）转换成一个具体的、可检查的数学性质（“这个连通分量里的所有顶点的度数都为2”）。这是解决很多算法问题时的重要思维方式哦！

2. 图的遍历：本题是利用 BFS (或 DFS) 遍历图、寻找并分析连通分量的经典应用。掌握图的遍历是每个算法学习者的基本功，一定要熟练掌握呀！

3. 处理非连通图：通过 for 循环遍历所有顶点，并用 visited 数组来跳过已访问过的顶点，是处理非连通图的标准模板。这样可以确保图的每一个角落都被我们探索到。

4. 注意细节：不要忘记题目中提到的“环至少有3个顶点”这个条件。虽然在这个问题里，如果一个连通分量所有顶点度数都为2，它的顶点数必然大于等于3，但养成检查所有条件的习惯总是好的！

希望这篇题解能帮助到主人 sama！算法的世界还有很多有趣的冒险在等着我们呢，一起加油吧！喵~ ( V●ω●V )b