BFS algorithm for checking bipartite graph

Question

I am confused why my code is producing wrong output.I am trying to do bfs for every node if it hasn't been visited yet, and trying to visit it's adj nodes too. Can anyone help me find the issue? here is my code:-

#include <bits/stdc++.h>
using namespace std;
int p = 1;
int ans[200005] = {-1};
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;
    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, i, ans))
                p = 0;
        }
    }
    if (!p)
        cout << "IMPOSSIBLE";
    else
    {
        for (int i = 1; i <= n; i++)
        {
            cout << ans[i] + 1 << ' ';
        }
    }
}

input :-

expected output:-

1 2 2 1 2

received output:-

1 1 1 1 1

`vector graph[n + 1];` isn't valid in standard conform C++. Why not `vector> graph(n + 1)`? — Scheff's Cat, Oct 17 '21 at 09:56
Why are you using `bits/stdc++.h`? That's only going to encourage you to write sloppy code. — Dai, Oct 17 '21 at 09:57
Don't use cryptic and short variable names. Your program code should be self-documenting. Also, your code is a mix of idiomatic C and C++ style and you're mutating global state. There's a lot of improve here... — Dai, Oct 17 '21 at 09:59
_Can anyone help me find the issue?_ Yes. This is what a debugger is good for. FYI: [SO: What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/7478597) — Scheff's Cat, Oct 17 '21 at 09:59
Please provide sample input, expected output for that input, and what you get instead. — trincot, Oct 17 '21 at 10:08
Related: [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [Why is "using namespace std;" considered bad practice](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice)? — Stef, Oct 17 '21 at 10:14
Also, what does *"I am confused why my code is producing wrong output."* mean exactly? What output is your code producing, and what did you expect it to produce instead? — Stef, Oct 17 '21 at 10:15
`vectorgraph[n+1]` and `bits/stdc++.h` and `using namespace std;` are not the issues — amar kumar, Oct 17 '21 at 10:29
I don't know why, but doing `for (int i=1;i<=n;i++)ans[i]=-1;` inside the main function helped get the answer. I had already initialized the whole `ans` array as -1 outside itself. — amar kumar, Oct 17 '21 at 10:33
_I had already initialized the whole ans array as -1 outside itself._ No, you didn't. Have a look at: [SO: Array doesn't initialize with a curly braces in c++](https://stackoverflow.com/q/20576162/7478597) to see why. Sorry, to insist on this... This wouldn't have happened with `std::vector` which you can construct with a size and a fill value. — Scheff's Cat, Oct 17 '21 at 11:27
@Dai can you pls focus on the main issue, if you can't solve, don't just divert the topic of discussion... — amar kumar, Jun 30 '23 at 14:43

Roger Smith · Accepted Answer · 2021-10-17T11:56:56.437

Your algorithm is fine

C array initialization does not initialize the whole array from a braced list initializer that contains just 1 element, except that it is 0.

int arr1[5] = {-1}; // -1, 0, 0, 0, 0
int arr1[5] = {0}; // 0, 0, 0, 0, 0

see https://stackoverflow.com/a/1065800/10911830

Here is fixed code, compacted the main function just not to waste screen space:

#include <vector> // for input
#include <iostream> // for debugging
#include <queue> // for bfs
#include <algorithm> // for std::fill_n
using namespace std;

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;
}
int main()
{   
    int p = 1;
    const int ANS_MAX = 200005;
    int ans[ANS_MAX];
    std::fill_n(ans, ANS_MAX , -1); // 1. array initialization
    int n, m;
    cin >> n >> m;
    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 && bfs(graph, i, ans)) p = 0;

    if (!p) cout << "IMPOSSIBLE";
    else for (int i = 1; i <= n; i++) cout << ans[i] + 1 << ' ';
    
   }

I did not test it with any other inputs, so there might be some bugs, but at least the main problems are fixed now.

BFS algorithm for checking bipartite graph

1 Answers1