时间戳

首页 > 解决方案 > 谁能发现该代码有什么问题？

graph - 谁能发现该代码有什么问题？

问题描述

我一直在尝试解决 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 上产生了错误的答案。谁能弄清楚我在那个代码中遗漏了什么？提前致谢。♥</p>

标签： graphbreadth-first-searchbipartite

解决方案

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

推荐阅读