| 1 | class Solution { |
| 2 | public: |
| 3 | bool bfs(vector<vector<int>> graph, vector<int> &vis, int src) |
| 4 | { |
| 5 | queue<int> q; |
| 6 | q.push(src); |
| 7 | int clr = 0; |
| 8 | while(!q.empty()) |
| 9 | { |
| 10 | int size = q.size(); |
| 11 | for(int i=0; i<size; i++) |
| 12 | { |
| 13 | int vrt = q.front(); |
| 14 | q.pop(); |
| 15 | if(vis[vrt]!=-1) |
| 16 | { |
| 17 | if(clr!=vis[vrt]) |
| 18 | return false; |
| 19 | continue; |
| 20 | } |
| 21 | vis[vrt]=clr; |
| 22 | for(int j=0; j<graph[vrt].size(); j++) |
| 23 | { |
| 24 | if(vis[graph[vrt][j]]==-1) |
| 25 | q.push(graph[vrt][j]); |
| 26 | } |
| 27 | } |
| 28 | clr = (clr+1)%2; |
| 29 | } |
| 30 | return true;; |
| 31 | } |
| 32 | bool isBipartite(vector<vector<int>>& graph) { |
| 33 | vector<int> vis(graph.size(),-1); |
| 34 | for(int i=0; i<graph.size(); i++) |