基于BFS算法的二分图检测代码输出错误排查

问题原因 #

• 全局数组初始化错误：你定义的int ans[200005] = {-1};在C++语法中仅会将第一个元素ans[0]赋值为-1，其余所有元素默认初始化为0。这就导致主函数中判断节点未访问的条件ans[i] == -1对1~n的所有节点都不成立，没有任何节点进入BFS流程做染色，最终输出ans[i]+1自然全为1，和你收到的实际输出一致。
• 可选优化点：vector<int> graph[n + 1]属于C可变长数组扩展，不符合C标准语法，兼容性差，建议替换为标准的vector<vector<int>>写法。

修复方案 #

在主函数读取n、m之后，添加memset(ans, -1, sizeof ans);手动将整个ans数组初始化为-1即可，完整修复后代码如下：

#include <bits/stdc++.h>
using namespace std;
int p = 1;
int ans[200005];
bool bfs(vector<int> graph[], int x, int ans[])
{
    queue<int> q;
    q.push(x);
    ans[x] = 1;
    while (!q.empty())
    {
        int f = q.front();
        q.pop();
        for (auto it : graph[f])
        {
            if (ans[it] == -1) {
                ans[it] = 1 - ans[f];
                q.push(it);
            } else if (ans[it] == ans[f]) {
                return true;
            }
        }
    }
    return false;
}
signed main()
{
    int n, m;
    cin >> n >> m;
    memset(ans, -1, sizeof ans);
    vector<vector<int>> graph(n + 1);
    for (int i = 1, a, b; i <= m; i++)
    {
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for (int i = 1; i <= n; i++)
    {
        if (ans[i] == -1)
        {
            if (bfs(graph.data(), i, ans))
                p = 0;
        }
    }
    if (!p)
        cout << "IMPOSSIBLE";
    else
    {
        for (int i = 1; i <= n; i++)
        {
            cout << ans[i] + 1 << ' ';
        }
    }
}

验证结果 #

用你提供的测试输入运行修复后代码，可正确得到预期输出1 2 2 1 2。

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