Its long but easy to understand(Hope it helps!)


#1

//Declaring adjacency list and the two required arrays
//globally to avoid passing in function parameters
vector adj[100001];
bool visited[100001];
bool colored[100001];

//Recursive Dfs function(If facing trouble try to think in terms of cycle in an undirected graph)
bool dfs(int src,int currentColor)
{
visited[src] = true;
colored[src] = currentColor;

for(auto i = adj[src].begin();i!=adj[src].end();i++){
    if(visited[*i]==false){
        bool problemMili = dfs(*i,!currentColor);
        if(problemMili)
            return true;
    }
    else if(colored[*i]==colored[src])
        return true;
}
return false;

}

int Solution::solve(int A, vector<vector > &B) {
//clearing the three global containers for each test case
memset(visited, false, sizeof visited);
memset(colored, false, sizeof colored);
for(int i=0;i<100001;i++)
adj[i].clear();
//Converting adjacency matrix to adjacency list
for(int i=0;i<B.size();i++){
adj[B[i][0]].push_back(B[i][1]);
adj[B[i][1]].push_back(B[i][0]);
}

bool currentColor = false;
bool isNonBiPartite = false;
//this for loop is to cover graphs with non connected comonents
for(int i=1;i<=A;i++){
    if(visited[i]==false)
    {
        isNonBiPartite =dfs(i,currentColor);
        if(isNonBiPartite)
            break;
    }
}
if(isNonBiPartite)
    return 0;
else
    return 1;

}