0

I am doing a simple BFS and marks the neighbouring elements for the vertices which comes under the current traversing vertice and if it's again found in the next vertices of the current traversing vertice then it's not a bipartite.

#include <bits/stdc++.h>

using namespace std;

vector<long> g[100000];

void neighbour(long it, vector<bool>& nei)
{
    for (auto itr : g[it])
        nei[itr] = true;
}

bool BFSbipartile(vector<bool>& vis, long v, long ver)
{
    queue<long> q;

    bool flag = true;
    q.push(v);
    vis[v] = true;
    while (!q.empty()) {
        long t = q.front();
        q.pop();
        vector<bool> nei(ver + 1, false);
        for (auto it : g[t]) {
            if (!vis[it]) {
                neighbour(it, nei);
                if (nei[it] == true) {
                    flag = false;
                    break;
                }
                vis[it] = true;
                q.push(it);
            }
            if (!flag)
                return false;
        }
    }
    return true;
}

int main()
{
    long v, e, e1, e2;
    cin >> v >> e;
    for (long i = 0; i < e; i++) {
        cin >> e1 >> e2;
        g[e1].push_back(e2);
        g[e2].push_back(e1);
    }
    vector<bool> vis(v + 1, false);
    bool tru = true;
    for (int i = 1; i <= v; i++) {
        if (!vis[i])
            tru = BFSbipartile(vis, i, v);
        if (!tru) {
            cout << 0 << endl;
            break;
        }
    }
    if (tru)
        cout << 1 << endl;

    return 0;
}
Marek R
  • 32,568
  • 6
  • 55
  • 140
user14153973
  • 9
  • 1
  • What is the name of the algorithm your trying to implement? – Surt Jan 07 '21 at 14:45
  • Does your algorithm give the wrong answer? Does it say bipartite graphs aren't bipartite, does it say that graphs are bipartite when they aren't, or does it make both of these mistakes? What is the "idea" behind your algorithm... why should it work? – Patrick87 Jan 07 '21 at 14:52
  • *What is wrong in my code for finding if a graph is Bipartite or not?* -- [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). Also [What is a debugger, and how does it help you diagnose problems](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – PaulMcKenzie Jan 07 '21 at 14:53
  • Welcome to StackOverflow. I suggest you improve your answer, have a look here → [How do I write a good answer?](https://stackoverflow.com/help/how-to-answer) Especially I suggest you, because of the nature of your question, to add the **unexpected output** you currently have or the **error** and the **expected Output** , so that other users can actually work on it – Federico Baù Jan 07 '21 at 15:59
  • I think it's your algorithm that goes wrong, rather than your code – Abhinav Mathur Jan 08 '21 at 04:48

0 Answers0