题目理解

我们有一个无向连通图，需要在图中找到若干个简单环（回路），要求：

1. 每个环都是简单环（起点和终点相同，且不重复经过顶点）
2. 所有环的边集互不相交
3. 所有环的边集并起来恰好覆盖图中的所有边

换句话说，我们需要将图的边集划分为若干个简单环。

问题转化

设图 $G = (V, E)$，其中 $|V| = n$，$|E| = m$。我们需要找到一组环 $C_1, C_2, \ldots, C_k$，使得：

• $\bigcup_{i=1}^k E(C_i) = E$
• $E(C_i) \cap E(C_j) = \emptyset$ 对于 $i \neq j$
• 每个 $C_i$ 都是简单环

算法思路

核心观察

这个问题实际上是在寻找图的边不相交的环覆盖。由于题目保证存在解，我们可以利用以下性质：

• 在DFS遍历过程中，当回溯时遇到已经在当前路径中的顶点，就说明找到了一个环
• 通过标记已访问的边，可以确保每条边只被一个环使用

算法步骤

1. DFS遍历：从任意顶点开始进行DFS遍历
2. 边标记：记录每条边是否被访问过（由于是无向图，每条边要标记两次）
3. 栈维护：使用栈来记录遍历路径
4. 环提取：当DFS回溯时，如果发现当前顶点在栈中已经出现过，说明找到了一个环，立即输出这个环

具体来说：

• 对于顶点 $u$，遍历其所有邻边
• 如果边 $(u,v)$ 未被访问，标记该边并递归访问 $v$
• 回溯时，如果 $u$ 已经在栈中，说明从栈顶到 $u$ 的路径形成了一个环
• 输出这个环，并将相关顶点从栈中移除

代码实现分析

#include <iostream>
#include <vector>
using namespace std;

const int N = 1e6 + 9;
int n, m, now[N], tot = 1, st[N], top;
bool vis[N], in[N];
vector<pair<int, int>> e[N];

void dfs(int u) {
    // 遍历u的所有邻边，使用now数组避免重复检查
    for (int i = now[u]; i < e[u].size(); i = now[u]) {
        auto t = e[u][i];
        now[u] = i + 1;  // 更新当前访问位置
        
        if (vis[t.second]) continue;  // 边已访问过
        
        vis[t.second] = vis[t.second ^ 1] = true;  // 标记边和反向边
        dfs(t.first);  // 递归遍历
    }
    
    // 回溯时检查环
    if (in[u]) {
        // 输出从栈顶到u的环
        while (st[top] != u) {
            int x = st[top];
            cout << x << " ";
            in[x] = false;
            top--;
        }
        cout << u << endl;
        top--;
    } else {
        in[u] = true;  // 标记u在栈中
    }
    
    st[++top] = u;  // u入栈
}

int main() {
    cin >> n >> m;
    
    // 建图，每条边分配唯一编号
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back({v, ++tot});
        e[v].push_back({u, ++tot});
    }
    
    dfs(1);  // 从顶点1开始DFS
    
    return 0;
}

关键技巧

• 边编号：每条无向边分配两个连续的编号，便于同时标记边和反向边
• now数组：记录每个顶点当前访问到了哪条边，避免重复检查，保证线性时间复杂度
• 栈机制：通过维护栈和in数组，可以在回溯时高效检测环
• 即时输出：检测到环后立即输出，避免额外存储

算法正确性证明

1. 完备性：DFS会遍历所有边，因为每次递归都会标记边为已访问，且now数组确保不遗漏
2. 环的正确性：当回溯时发现顶点已在栈中，从栈顶到该顶点的路径必然形成简单环
3. 边覆盖：所有边都被标记访问，且每条边只属于一个环
4. 环的简单性：DFS保证不重复访问顶点（通过栈机制）

复杂度分析

• 时间复杂度：$O(n + m)$，每个顶点和每条边只被处理一次
• 空间复杂度：$O(n + m)$，用于存储邻接表、栈和标记数组

样例解释

对于样例输入：

10 15
1 3
5 1
2 3
9 2
3 4
6 3
4 5
7 4
4 8
5 7
8 5
6 7
7 8
8 10
10 9

输出：

2 3 4 5 8 10 9
7 8 4  
1 5 7 6 3

这表示找到了3个简单环：

• 环1: 2→3→4→5→8→10→9→2
• 环2: 7→8→4→7
• 环3: 1→5→7→6→3→1

三个环的边集互不相交且覆盖了所有15条边。

算法标签

• 图论
• DFS遍历
• 环检测
• 欧拉回路分解
• 栈应用

总结

本题的关键在于理解图的环分解，利用DFS的回溯特性来检测和输出简单环。算法通过巧妙的边标记和栈维护机制，实现了高效且简洁的解决方案，能够处理大规模数据（$n, m \leq 500,000$）。核心思想是将边不相交的环覆盖问题转化为DFS过程中的环检测问题。