C++实现无向图双连通分量运行报0xC0000005错误求排查

错误原因 #

• 第一个致命错误：while循环判断顺序错误
  你写的while(s.top() != vecin && (!(s.empty())) && (s.size() > 0))逻辑判断顺序完全颠倒，C++的&&运算符从左到右短路求值，栈为空时会先执行s.top()访问空栈的栈顶，直接触发内存访问违规（即你遇到的0xC0000005错误），你写的非空校验完全没有起到作用。
• 第二个逻辑错误：双连通分量的弹出判断位置错误
  if(nivelMin[vecin] >= nivel[nod])这个判断仅适用于未访问过的子节点（即树边对应的vecin），你把判断写在了所有邻边的处理逻辑外，回边的情况也会触发栈弹出操作，导致栈元素被错误提前弹出，后续必然出现空栈访问。
• 第三个遗漏逻辑：根节点需要特殊判断，且dfs结束后栈中剩余的节点属于最后一个双连通分量，你没有处理。

修复后的代码 #

#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

ifstream in("zao.in");
const int nmax = 1005;
int nivel[nmax];
vector<int> v[nmax];
bool viz[nmax];
int nivelMin[nmax];
stack<int> s;
int root;

void dfs(int nod, int parent){
    viz[nod] = true;
    nivelMin[nod] = nivel[nod];
    s.push(nod);
    int child = 0;
    for(auto vecin: v[nod]){
        if(vecin == parent) continue; // 跳过父节点，避免重复处理
        if(viz[vecin] == false)
        {
            child++;
            nivel[vecin] = nivel[nod] + 1;
            dfs(vecin, nod);
            nivelMin[nod] = min(nivelMin[nod], nivelMin[vecin]);
            // 仅对树边的子节点做割点判断和栈弹出操作
            if((nod == root && child > 1) || (nod != root && nivelMin[vecin] >= nivel[nod])){
                cout << "找到一个双连通分量: ";
                // 调整判断顺序，先判断栈非空再访问栈顶
                while(!s.empty() && s.top() != vecin)
                {
                    cout << s.top() << " ";
                    s.pop();
                }
                cout << s.top() << " " << nod << endl;
                s.pop(); // 弹出vecin
            }
        }
        else // 回边
        {
            nivelMin[nod] = min(nivelMin[nod], nivel[vecin]);
        }
    }
}

int main()
{
    int n, m;
    in >> n >> m;
    for(int i = 0; i < m; ++i)
    {
        int x, y;
        in >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    // 处理不连通的图
    for(int i=1;i<=n;i++){
        if(!viz[i]){
            root = i;
            nivel[root] = 1;
            dfs(root, -1);
            // 弹出栈中剩余的最后一个分量
            cout << "找到一个双连通分量: ";
            while(!s.empty()){
                cout << s.top() << " ";
                s.pop();
            }
            cout << endl;
        }
    }
    
    return 0;
}

测试输出 #

对给出的zao.in测试用例，运行修复后的代码输出如下：

找到一个双连通分量: 3 2 
找到一个双连通分量: 4 5 2 1 
找到一个双连通分量: 6 8 7 5 

内容的提问来源于stack exchange，提问作者Johnny