SHARE
TWEET

Untitled

bbescos Feb 27th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. // 0 1 0 1 0 1 0
  7. // 1 0 1 0 1 0 1
  8. // 0 1 0 0 0 1 0
  9. // 1 0 1 0 1 0 1
  10.  
  11. struct Point {
  12.   int x;
  13.   int y;
  14.   Point(int x, int y) : x(x), y(y) {};
  15. };
  16.  
  17. bool InMap(const vector<vector<int>>& map, const Point& p) {
  18.   return (p.x >= 0 && p.x < map.size() && p.y >= 0 && p.y < map[0].size());
  19. }
  20.  
  21. // Check if a graph is bipartite
  22. bool IsBipartite (const vector<vector<int>>& map) {
  23.  
  24.   vector<vector<bool>> visited_map(map.size(), vector<bool> (map[0].size(), false));
  25.  
  26.   vector<vector<int>> neighbors_map{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
  27.  
  28.   queue<Point> q_points;
  29.   Point first_point(0, 0);
  30.   q_points.push(first_point);
  31.   visited_map[0][0] = true;
  32.  
  33.   while (!q_points.empty()) {
  34.     Point current = q_points.front();
  35.     q_points.pop();
  36.    
  37.     for (int i = 0; i < 4; ++i) {
  38.       Point neighbor(current.x + neighbors_map[i][0], current.y + neighbors_map[i][1]);
  39.       if (InMap(map, neighbor) && !visited_map[neighbor.x][neighbor.y]) {
  40.         if (map[neighbor.x][neighbor.y] != map[current.x][current.y]) {
  41.           q_points.push(neighbor);
  42.           visited_map[neighbor.x][neighbor.y] = true;
  43.         }
  44.         else
  45.           return false;
  46.       }
  47.     }
  48.    
  49.   }
  50.  
  51.   return true;
  52. }
  53.  
  54.  
  55. int main() {
  56.  
  57.   vector<vector<int>> map{{0, 1, 0, 1, 0, 1, 0},
  58.                           {1, 0, 1, 0, 1, 0, 1},
  59.                           {0, 1, 0, 0, 0, 1, 0},
  60.                           {1, 0, 1, 0, 1, 0, 1}};
  61.  
  62.   cout << IsBipartite(map) << endl;
  63.  
  64.  
  65.   return 0;
  66. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top