任何人都可以发现该代码有什么问题吗？

Question

我一直在尝试解决来自 coursera 的问题。

问题描述：给定一个有顶点和边的无向图，检查它是否是二分图。

输入格式。图表以标准格式给出。

约束。 1 ≤ ≤ 105，0 ≤ ≤ 105。输出格式。如果图是二分图则输出 1，否则输出 0。

Input:
4 4
1 2
4 1
2 3
3 1
Output:
0
Input:
5 4
5 2
4 2
3 4
1 4
Output:
1

我想出了一个 C++ 解决方案，看起来像

#include <bits/stdc++.h>
using namespace std;
#define vvi vector<vector<int>>
#define vi vector<int>
#define qi queue<int>
int bfs(vvi adj, int s, vi &disc, vi &dist)
{
    disc[s] = 1; dist[s] = 0;
    qi q;
    q.push(s);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int i: adj[u])
        {
            if(!disc[i])
            {
                disc[i] = 1;
                q.push(i);
                dist[i] = dist[u]+1;
            }else if(dist[u]==dist[i])
            {
                return 0;
            }
        }
    }
    return 1;
}
bool isBipartite(vvi adj, vi &disc, vi &dist)
{
    for(int i=0;i<adj.size();++i)
    {
        if(!disc[i])
        {
            if(!bfs(adj, i, disc, dist))
            {
                return 0;
            }
        }
    }
    return 1;
}
int main()
{
    int n, m;
    cin >> n >> m;
    vvi adj(n);
    for(int i=0;i<m;++i)
    {
        int x, y;
        cin >> x >> y;
        adj[x-1].push_back(y-1);
        adj[y-1].push_back(x-1);
    }
    vi dist(n);
    vi disc(n, 0);
    cout << isBipartite(adj, disc, dist);
 
}

但是这个解决方案在测试用例 3 上生成了错误的答案。有人能找出我在该代码中遗漏了什么吗？提前致谢。 ♥

Answer 1

你的逻辑似乎完美无缺，有一个可能的错误原因：你没有传递 adj 参数作为参考。这意味着对于 bfs 方法的每次调用都会复制图形。如果第三个测试用例是一个孤立的图（没有边）那将是糟糕的。有时runtime error和memory exceeded error被在线判断为不存在的错误答案。

任何人都可以发现该代码有什么问题吗？

Can anyone spot what is wrong with that code?

graph

breadth-first-search

bipartite