class Solution {
public:
bool checkneighbour(vector<int>&arr,vector<vector<int>>&adj,int item){
for(int x:arr){
for(int y:adj[x]){
if(y==item)return true;
}
}
return false;
}
bool ans(vector<vector<int>>&adj,int V){
queue<int>q;
vector<int>one;
vector<int>two;
vector<int>visited(V,0);
q.push(0);
visited[0]=1;
while(!q.empty()){
int x=q.front();
if(!checkneighbour(one,adj,x))one.push_back(x);
else if(!checkneighbour(two,adj,x))two.push_back(x);
else return false;
q.pop();
for(int y:adj[x] ){
if(!visited[y]){
q.push(y);
visited[y]=1;
};
}
}
return true;
}
bool isBipartite(int V, vector<vector<int>> &edges) {
// Code here
vector<vector<int>> adj(V);
for(auto& e : edges){
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
return ans(adj, V);
}
};
No comments:
Post a Comment