Bipartite graph c++

Question

I must check whether a graph represented by a given adjacency matrix is a bipartite graph. I wrote some code, but it always returns false for the test adjacency matrix below, for which it should return true.

Input:

10

0 1 0 0 1 0 0 0 0 0

1 0 0 0 0 0 0 0 0 0

0 0 0 1 0 0 1 1 0 1

0 0 1 0 0 1 0 0 1 0

1 0 0 0 0 0 0 0 0 0

0 0 0 1 0 0 0 1 0 1

0 0 1 0 0 0 0 0 1 0

0 0 1 0 0 1 0 0 1 0

0 0 0 1 0 0 1 1 0 0

0 0 1 0 0 1 0 0 0 0

Output:

YES
1 3 6 9

Code:

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

bool bipartite=true;
vector<vector<int>>g;
vector<int>visit;
vector<int>colour;
int n;

void dfs(int v)
{
    visit[v] = 1;
    if (colour[v] == 0)
    {
        colour[v] = 1;
    }
    for (int i = 0; i < g[v].size(); i++)
    {
        if (visit[i] == 0)
        {
            if (colour[v] == 1)
            {
                colour[i] = 2;
            }
            else
                colour[i] = 1;
            dfs(i);
        }       
        if (visit[i] == 1 && colour[i] == colour[v])
            bipartite = false;
    }

}

int main()
{
    ifstream fin("input.in");
    ofstream fout("output.out");
    int a;

    fin >> n;
    g.resize(n);    
    visit.resize(n);
    colour.resize(n);   

    for (int i = 0; i < g.size(); i++)
    {       
        for (int j = 0; j < n; j++)
        {
            fin >> a;           
            g[i].push_back(a);
        }
    }

    for (int i = 0; i < n; i++)
    {       
        if (visit[i] == 0)
            dfs(i);
    }

    cout << bipartite;

    return 0;
}

Answer 1

This should solve your problem. Try to find out why my code works even though it is almost the same as yours.

Hint: Think about the if (visit[i] == 0) statement you wrote in the dfs function

#include <iostream>    
#include <fstream>    
#include <vector>    
#include <queue>    

using namespace std;    

bool bipartite=true;    
vector<vector<int> > g;    
vector<int>visit;    
vector<int>colour;    
int n;    

void dfs(int v, int p)    
{    
    visit[v] = 1;    
    colour[v] = p;    

    for (int i = 0; i < g[v].size(); i++)    
    {    
        if(g[v][i]) {    
            if (visit[i] == 0) {    
                dfs(i, 1-p);    
            } else {    
                if(colour[i] == colour[v]) 
                    bipartite = false;
            }    
        }    
    }    
}    


int main()    
{    
    ifstream fin("input.in");    
    ofstream fout("output.out");    
    int a;    

    fin >> n;    
    g.resize(n);        
    visit.resize(n);    
    colour.resize(n);       

    for (int i = 0; i < g.size(); i++)    
    {           
        for (int j = 0; j < n; j++)    
        {    
            fin >> a;               
            g[i].push_back(a);    
        }    
    }    

    for (int i = 0; i < n; i++)    
    {           
        if (visit[i] == 0)    
            dfs(i, 0);    
    }    

    for(int i=0; i<n; ++i)  {  
        if(colour[i] == 1) cout << i << " ";
    }
    cout << endl;    

    for(int i=0; i<n; ++i)  {  
        if(colour[i] == 0) cout << i << " ";
    }
    cout << endl;    

    cout << "Is bipartite: " << bipartite << endl;    

    return 0;    
}