C++ 无向连通图找到所有环并删除使用非递归代码

在无向图中，找到所有环并删除可以使用拓扑排序的思想。具体地，对于每个节点，记录它的入度（即有多少条边指向它），然后从入度为 0 的节点开始进行拓扑排序。每次找到一个入度为 0 的节点，就将其从图中删除，并将其相邻节点的入度减 1。如果在这个过程中发现有节点的入度为 0 但还没有被删除，说明这个节点与之前已经删除的节点构成了一个环。

下面是使用非递归方式找到无向图中所有环并删除的 C++ 代码示例：

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

const int MAXN = 1000;  // 图中最大节点数

vector<int> graph[MAXN];  // 邻接表存储图的信息
int in_degree[MAXN];      // 记录每个节点的入度

// 找到所有环并删除
void find_and_remove_cycles(int n) {
    queue<int> q;  // 用队列来实现拓扑排序
    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : graph[u]) {
            if (--in_degree[v] == 0) {
                q.push(v);
            }
        }
        // 判断是否有环
        if (in_degree[u] == 0) {
            cout << "Found cycle: " << u << " ";
            in_degree[u] = -1;  // 将入度设为 -1 表示已经删除
            for (int v : graph[u]) {
                if (in_degree[v] != -1) {
                    in_degree[v]--;
                }
            }
        }
    }
}

int main() {
    int n, m;  // n 为节点数，m 为边数
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);  // 无向图需要将两个方向都存储
        in_degree[u]++;
        in_degree[v]++;
    }

    // 找到所有环并删除
    find_and_remove_cycles(n);

    // 输出删除环后的图
    for (int u = 1; u <= n; ++u) {
        if (in_degree[u] != -1) {
            cout << u << ": ";
            for (int v : graph[u]) {
                if (in_degree[v] != -1) {
                    cout << v << " ";
                }
            }
            cout << endl;
        }
    }

    return 0;
}

该程序读入图中的节点数和边数，然后读入每一条边的信息，构建出邻接表，并记录每个节点的入度。接着调用 `find_and_remove_cycles` 函数，对图进行拓扑排序并找到所有环并删除。最后输出删除环后的图的信息。

注意，在找到一个环并删除后，需要将环中的所有节点的入度减 1，避免重复找到环。