Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- bool isBipartite(vector<vector<int>>& graph) {
- if(graph.size()==0){
- return false;
- }
- unordered_set<int>first_set;
- unordered_set<int>second_set;
- queue<int>to_process_children;
- unordered_set<int>already_used;
- int first_nenul=0;
- to_process_children.push(first_nenul);
- first_set.insert(first_nenul);
- while(!to_process_children.empty()){
- int front = to_process_children.front();
- to_process_children.pop();
- if(already_used.find(front)!=already_used.end()){
- continue;
- }
- if(graph[front].size()==0){
- continue;
- }
- if(first_set.find(front)!=first_set.end()){
- second_set.insert(graph[front].begin(), graph[front].end());
- }
- else{
- first_set.insert(graph[front].begin(), graph[front].end());
- }
- for(int i=0; i<graph[front].size();i++){
- to_process_children.push(graph[front][i]);
- }
- already_used.insert(front);
- }
- for(int i=0; i<graph.size();i++){
- if(first_set.find(i)!=first_set.end() && second_set.find(i)!= second_set.end()){
- return false;
- }
- }
- return true;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement