Solution Explanation!


#1

EZ simple , refer comments for explanations :grin:

int check(int A, vector<vector > &adj ){

int n = A;
vector<int> side(n, -1);
bool is_bipartite = true;
queue<int> q; // for performing bfs checks on each node
for (int st = 0; st < n; ++st) {
    if (side[st] == -1) {
        
        q.push(st);
        side[st] = 0; // give it a color/ 0
        while (!q.empty()) {
            int v = q.front(); // store and then pop the 1st one
            q.pop();
            for (int u : adj[v]) { //hello my child
                if (side[u] == -1) { // have u never been visited by me(current node)
                    side[u] = side[v] ^ 1; // Take my reverse color / xor or mine
                    q.push(u); // now lemme push u inside again so that queue can explore ur >connections
                } else {// oh !! have i visited u before my son ?
                    is_bipartite &= (side[u] != side[v]);          // lemme match my color with urs !!
                    if(is_bipartite == false)           //  if mine and ur color are the same then !! 
                        return 0;           // Mission Failed !!
                }
            }
        }
    }
}
return (is_bipartite ? 1 : 0);

}

int Solution::solve(int A, vector<vector > &B) {

     vector<vector<int>> adj(A);
for(auto v:B){

// 0 indexing OCD XD
adj[v[0]-1].push_back(v[1]-1);
adj[v[1]-1].push_back(v[0]-1);
}

return check(A, adj);

}