SHARE
TWEET

Untitled

a guest Dec 15th, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <queue>
  3. #include <fstream>
  4. #include <iomanip>
  5. #include <time.h>
  6.  
  7. using namespace std;
  8.  
  9. vector<pair<vector<int>, vector<int> > > teams;
  10.  
  11. bool cmp(pair<vector<int>, vector<int> > a, pair<vector<int>, vector<int> > b) {
  12.     if (a.first.size() > b.first.size() && a.first.size() > b.second.size()) {
  13.         return 1;
  14.     }
  15.     if (a.second.size() > b.first.size() && a.second.size() > b.second.size()) {
  16.         return 1;
  17.     }
  18.     return 0;
  19.  
  20. }
  21.  
  22. //bool Search(vector<int> &color, int key)
  23. //{
  24. //    for (int i = 0; i < color.size(); i++)
  25. //        if (color[i] == key)
  26. //            return true;
  27. //    return false;
  28. //}
  29.  
  30. bool isBipart(vector<vector<int>>& g, int startNode, vector<int>& colorArr, int n)
  31. {
  32.     n = g.size();
  33.     colorArr[startNode] = 1;
  34.     vector<int> firstTeam;
  35.     vector<int> secondTeam;
  36.     firstTeam.push_back(startNode);
  37.  
  38.     queue <int> q;
  39.     q.push(startNode);
  40.  
  41.     while (!q.empty())
  42.     {
  43.         int v = q.front();
  44.         q.pop();
  45.  
  46.         // Return false if there is a self-loop
  47.         //can be deleted, only for this task, because there is no self-loops
  48.  
  49.         if (g[v][v])
  50.             return false;
  51.  
  52.         // Find all non-colored adjacent vertices
  53.         for (int i = 0; i < n; i++)
  54.         {
  55.             //-1 - non-colored
  56.             //0 - first color, 1 - second color
  57.  
  58.             if (g[v][i] && colorArr[i] == -1)
  59.             {
  60.                 colorArr[i] = 1 - colorArr[v];
  61.                 if (colorArr[i] == 0) {
  62.                     secondTeam.push_back(i);
  63.                 }
  64.                 else {
  65.                     firstTeam.push_back(i);
  66.                 }
  67.                 q.push(i);
  68.             }
  69.  
  70.             else if (g[v][i] && colorArr[i] == colorArr[v])
  71.                 return false;
  72.         }
  73.     }
  74.     teams.push_back(make_pair(firstTeam, secondTeam));
  75.     // If we reach here, then all adjacent vertices can
  76.     // be colored with alternate color
  77.     return true;
  78. }
  79.  
  80. bool isBipartite(vector<vector<int>>& g, vector<int>& color)
  81. {
  82.     int n = g.size();
  83.     color.assign(n, -1);
  84.  
  85.     // This code is to handle disconnected graph
  86.     for (int i = 0; i < n; i++)
  87.         if (color[i] == -1)
  88.             if (!isBipart(g, i, color, n))
  89.                 return false;
  90.     return true;
  91. }
  92.  
  93. int main()
  94. {
  95.     ifstream cin("input.in");
  96.     //ofstream cout("output.out");
  97.     srand(time(NULL));
  98.     int n;
  99.     bool _isBipartite;
  100.     cin >> n;
  101.     vector<vector<int>> g(n, vector<int>(n));
  102.     vector<int> color(n);
  103.  
  104.     for (int i = 0; i < n; i++)
  105.     {
  106.         for (int j = 0; j < n; j++)
  107.         {
  108.             int value;
  109.             cin >> value;
  110.  
  111.             if (i == j)
  112.                 continue;
  113.  
  114.             if (value)
  115.                 g[i][j] = 0;
  116.             else
  117.                 g[i][j] = 1;
  118.         }
  119.     }
  120.     _isBipartite = isBipartite(g, color); // if the graph is bipartite? true / false
  121.  
  122.  
  123.     if (_isBipartite)
  124.     {
  125.         sort(teams.begin(), teams.end(), cmp);
  126.         vector<int> realFirstTeam;
  127.         vector<int> realSecondTeam;
  128.         int countFirstTeamMembers = 0, countSecondTeamMembers = 0; //first team - 0, second - 1.
  129.         for (int i = 0; i < teams.size(); i++) {
  130.             bool flag = false;
  131.             if (teams[i].first.size() <= teams[i].second.size()) {
  132.                 flag = true;
  133.             }
  134.             if (realFirstTeam.size() <= realSecondTeam.size()) {
  135.                 if (!flag) {
  136.                     for (int j = 0; j < teams[i].first.size(); j++) {
  137.                         realFirstTeam.push_back(teams[i].first[j]);
  138.                     }
  139.                     for (int j = 0; j < teams[i].second.size(); j++) {
  140.                         realSecondTeam.push_back(teams[i].second[j]);
  141.                     }
  142.                 }
  143.                 else {
  144.                     for (int j = 0; j < teams[i].first.size(); j++) {
  145.                         realSecondTeam.push_back(teams[i].first[j]);
  146.                     }
  147.                     for (int j = 0; j < teams[i].second.size(); j++) {
  148.                         realFirstTeam.push_back(teams[i].second[j]);
  149.                     }
  150.                 }
  151.             }
  152.             else {
  153.                 if (!flag) {
  154.                     for (int j = 0; j < teams[i].first.size(); j++) {
  155.                         realSecondTeam.push_back(teams[i].first[j]);
  156.                     }
  157.                     for (int j = 0; j < teams[i].second.size(); j++) {
  158.                         realFirstTeam.push_back(teams[i].second[j]);
  159.                     }
  160.                 }
  161.                 else {
  162.                     for (int j = 0; j < teams[i].first.size(); j++) {
  163.                         realFirstTeam.push_back(teams[i].first[j]);
  164.                     }
  165.                     for (int j = 0; j < teams[i].second.size(); j++) {
  166.                         realSecondTeam.push_back(teams[i].second[j]);
  167.                     }
  168.                 }
  169.             }
  170.         }
  171.         countFirstTeamMembers = realFirstTeam.size();
  172.         countSecondTeamMembers = realSecondTeam.size();
  173.         sort(realFirstTeam.begin(), realFirstTeam.end());
  174.         sort(realSecondTeam.begin(), realSecondTeam.end());
  175.         if (countFirstTeamMembers > 2 * countSecondTeamMembers || countSecondTeamMembers > 2 * countFirstTeamMembers)
  176.             cout << "NO";
  177.         else
  178.         {
  179.             if (countFirstTeamMembers > countSecondTeamMembers)
  180.             {
  181.                 cout << "YES" << endl;
  182.                 for (int i = 0; i < realFirstTeam.size(); i++) {
  183.                     cout << realFirstTeam[i] + 1 << ' ';
  184.                 }
  185.             }
  186.             else
  187.             {
  188.                 cout << "YES" << std::endl;
  189.                 for (int i = 0; i < realSecondTeam.size(); i++) {
  190.                     cout << realSecondTeam[i] + 1 << ' ';
  191.                 }
  192.             }
  193.         }
  194.     }
  195.     else
  196.         cout << "NO" << endl;
  197. }
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