SHARE
TWEET

Untitled

a guest Sep 18th, 2019 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. ifstream in;
  6. ofstream out;
  7.  
  8. int color[101];
  9.  
  10. bool isBipartite(int n,int a[][101], int src)
  11. {
  12.     for (int i = 1; i <= n; ++i)
  13.         color[i] = -1;
  14.  
  15.     color[src] = 1;
  16.  
  17.     queue <int> q;
  18.     q.push(src);
  19.  
  20.     while (!q.empty())
  21.     {
  22.         int u = q.front();
  23.         q.pop();
  24.  
  25.         if (a[u][u] == 1)
  26.             return false;
  27.  
  28.         for (int j = 1; j <= n; j++)
  29.         {
  30.            
  31.             if (a[u][j] && color[j] == -1)
  32.             {
  33.                 color[j] = 1 - color[u];
  34.                 q.push(j);
  35.             }
  36.  
  37.             else if (a[u][j] && color[j] == color[u])
  38.                 return false;
  39.         }
  40.     }
  41.  
  42.     return true;
  43. }
  44.  
  45. int n, m, x, y, i, j, k, a[101][101];
  46.  
  47. int main()
  48. {
  49.     in.open("bipartit1.in");
  50.     out.open("bipartit1.out");
  51.  
  52.     in >> n >> m;
  53.     for (i = 1; i <= m; i++)
  54.     {
  55.         in >> x >> y;
  56.         a[x][y] = a[y][x] = 1;
  57.     }
  58.    
  59.     bool ok;
  60.     ok = isBipartite(n, a, 1);
  61.     if (ok)
  62.     {
  63.         out << "DA" << endl;
  64.         for (i = 1; i <= n; i++)
  65.             if (color[1] == color[i])
  66.                 out << i << " ";
  67.         out << endl;
  68.         for (i = 1; i <= n; i++)
  69.             if (color[1] != color[i])
  70.                 out << i << " ";
  71.     }
  72.     else
  73.         out << "NU";
  74.  
  75.     in.close();
  76.     out.close();
  77.     return 0;
  78. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top