Niloy007

Bipartite Problem

Jun 19th, 2020
107
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define max 100000
  4. vector<int> graph[max];
  5. vector<int> visited;
  6. int color[max];
  7.  
  8.  
  9. bool dfs(int v, int c) {
  10.     visited[v] = 1;
  11.     color[v] = c;
  12.  
  13.     for(int child : graph[v]) {
  14.         if(visited[child] == 0) {
  15.             bool result = dfs(child, c ^ 1);
  16.             if(!result) {
  17.                 return false;
  18.             }
  19.         } else if(color[child] == color[v]) {
  20.             return false;
  21.         }
  22.     }
  23.     return true;
  24. }
  25.  
  26.  
  27.  
  28. int main() {
  29.     int t, v, e, count(1);
  30.     int a, b;
  31.     cin >> t;
  32.     while (t--) {
  33.         cin >> v >> e;
  34.  
  35.         visited.assign(v + 3, 0);
  36.         for(int i = 1; i <= v; i++) {
  37.             graph[i].clear();
  38.         }
  39.  
  40.         for (int i = 0; i < e; i++) {
  41.             cin >> a >> b;
  42.             graph[a].push_back(b);
  43.             graph[b].push_back(a);
  44.         }
  45.  
  46.         bool flag = true;
  47.  
  48.         for(int i = 1; i <= v; i++) {
  49.             if(visited[i] == 0) {
  50.                 bool bicolorable = dfs(i, 0);
  51.                 if(!bicolorable) {
  52.                     flag = false;
  53.                     break;
  54.                 }
  55.             }
  56.         }
  57.  
  58.         printf("Is bipartite?\n");
  59.         if(flag)
  60.             printf("Yes\n");
  61.         else
  62.             printf("NO\n");
  63.     }
  64.  
  65.     return 0;
  66. }
RAW Paste Data