Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <fstream>
- #include <iomanip>
- #include <time.h>
- using namespace std;
- vector<pair<vector<int>, vector<int> > > teams;
- bool cmp(pair<vector<int>, vector<int> > a, pair<vector<int>, vector<int> > b) {
- if (a.first.size() > b.first.size() && a.first.size() > b.second.size()) {
- return 1;
- }
- if (a.second.size() > b.first.size() && a.second.size() > b.second.size()) {
- return 1;
- }
- return 0;
- }
- //bool Search(vector<int> &color, int key)
- //{
- // for (int i = 0; i < color.size(); i++)
- // if (color[i] == key)
- // return true;
- // return false;
- //}
- bool isBipart(vector<vector<int>>& g, int startNode, vector<int>& colorArr, int n)
- {
- n = g.size();
- colorArr[startNode] = 1;
- vector<int> firstTeam;
- vector<int> secondTeam;
- firstTeam.push_back(startNode);
- queue <int> q;
- q.push(startNode);
- while (!q.empty())
- {
- int v = q.front();
- q.pop();
- // Return false if there is a self-loop
- //can be deleted, only for this task, because there is no self-loops
- if (g[v][v])
- return false;
- // Find all non-colored adjacent vertices
- for (int i = 0; i < n; i++)
- {
- //-1 - non-colored
- //0 - first color, 1 - second color
- if (g[v][i] && colorArr[i] == -1)
- {
- colorArr[i] = 1 - colorArr[v];
- if (colorArr[i] == 0) {
- secondTeam.push_back(i);
- }
- else {
- firstTeam.push_back(i);
- }
- q.push(i);
- }
- else if (g[v][i] && colorArr[i] == colorArr[v])
- return false;
- }
- }
- teams.push_back(make_pair(firstTeam, secondTeam));
- // If we reach here, then all adjacent vertices can
- // be colored with alternate color
- return true;
- }
- bool isBipartite(vector<vector<int>>& g, vector<int>& color)
- {
- int n = g.size();
- color.assign(n, -1);
- // This code is to handle disconnected graph
- for (int i = 0; i < n; i++)
- if (color[i] == -1)
- if (!isBipart(g, i, color, n))
- return false;
- return true;
- }
- int main()
- {
- ifstream cin("input.in");
- //ofstream cout("output.out");
- srand(time(NULL));
- int n;
- bool _isBipartite;
- cin >> n;
- vector<vector<int>> g(n, vector<int>(n));
- vector<int> color(n);
- for (int i = 0; i < n; i++)
- {
- for (int j = 0; j < n; j++)
- {
- int value;
- cin >> value;
- if (i == j)
- continue;
- if (value)
- g[i][j] = 0;
- else
- g[i][j] = 1;
- }
- }
- _isBipartite = isBipartite(g, color); // if the graph is bipartite? true / false
- if (_isBipartite)
- {
- sort(teams.begin(), teams.end(), cmp);
- vector<int> realFirstTeam;
- vector<int> realSecondTeam;
- int countFirstTeamMembers = 0, countSecondTeamMembers = 0; //first team - 0, second - 1.
- for (int i = 0; i < teams.size(); i++) {
- bool flag = false;
- if (teams[i].first.size() <= teams[i].second.size()) {
- flag = true;
- }
- if (realFirstTeam.size() <= realSecondTeam.size()) {
- if (!flag) {
- for (int j = 0; j < teams[i].first.size(); j++) {
- realFirstTeam.push_back(teams[i].first[j]);
- }
- for (int j = 0; j < teams[i].second.size(); j++) {
- realSecondTeam.push_back(teams[i].second[j]);
- }
- }
- else {
- for (int j = 0; j < teams[i].first.size(); j++) {
- realSecondTeam.push_back(teams[i].first[j]);
- }
- for (int j = 0; j < teams[i].second.size(); j++) {
- realFirstTeam.push_back(teams[i].second[j]);
- }
- }
- }
- else {
- if (!flag) {
- for (int j = 0; j < teams[i].first.size(); j++) {
- realSecondTeam.push_back(teams[i].first[j]);
- }
- for (int j = 0; j < teams[i].second.size(); j++) {
- realFirstTeam.push_back(teams[i].second[j]);
- }
- }
- else {
- for (int j = 0; j < teams[i].first.size(); j++) {
- realFirstTeam.push_back(teams[i].first[j]);
- }
- for (int j = 0; j < teams[i].second.size(); j++) {
- realSecondTeam.push_back(teams[i].second[j]);
- }
- }
- }
- }
- countFirstTeamMembers = realFirstTeam.size();
- countSecondTeamMembers = realSecondTeam.size();
- sort(realFirstTeam.begin(), realFirstTeam.end());
- sort(realSecondTeam.begin(), realSecondTeam.end());
- if (countFirstTeamMembers > 2 * countSecondTeamMembers || countSecondTeamMembers > 2 * countFirstTeamMembers)
- cout << "NO";
- else
- {
- if (countFirstTeamMembers > countSecondTeamMembers)
- {
- cout << "YES" << endl;
- for (int i = 0; i < realFirstTeam.size(); i++) {
- cout << realFirstTeam[i] + 1 << ' ';
- }
- }
- else
- {
- cout << "YES" << std::endl;
- for (int i = 0; i < realSecondTeam.size(); i++) {
- cout << realSecondTeam[i] + 1 << ' ';
- }
- }
- }
- }
- else
- cout << "NO" << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement