Advertisement
Oppenheimer

Bipartite matching

Aug 19th, 2022
25
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.69 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     bool bp = true;
  4.     void dfs(int node , vector<vector<int>>&g , vector<int>&color){
  5.         for(int x : g[node]){
  6.             if(color[x] == -1){
  7.                 color[x] = 1-color[node];
  8.                 dfs(x,g,color);
  9.             }
  10.             else if(color[x] == color[node]){
  11.                 bp = false;
  12.             }
  13.         }
  14.     }
  15.     bool isBipartite(vector<vector<int>>& graph) {
  16.        
  17.         int n = graph.size();
  18.         vector<int>color(n,-1);
  19.         for(int a=0;a<n;a++){
  20.             if(color[a] == -1){
  21.                 color[a] = 0;
  22.                 dfs(a,graph,color);
  23.             }
  24.         }
  25.        
  26.         return bp;
  27.     }
  28. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement