Building Teams

input/code.cpp: In function 'bool bipartite(std::vector<std::vector<int> >&, int, int, std::vector<bool>&)':
input/code.cpp:34:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |                 for (int i = 0; i
      |                                 ~                
   34 |                                                 < edges[current].size();
      |                                                 ^~~~~~~~~~~~~~~~~~~~~~~

#include <bits/stdc++.h>
using namespace std;

unordered_set<int> sets[2];

bool bipartite(vector<vector<int> >& edges,
			int V, int i,
			vector<bool>& visited)
{
	if (V == 0) {
		return true;
	}
	vector<int> pending;

	sets[0].insert(i);

	pending.push_back(i);
	while (pending.size() > 0) {

		int current = pending.back();

		// Mark the current vertex true
		visited[current] = true;
		pending.pop_back();

		// Finding the set of
		// current vertex(parent vertex)
		int currentSet
			= sets[0].count(current)
					> 0
				? 0
				: 1;
		for (int i = 0; i
						< edges[current].size();
			i++) {

			// Picking out neighbour
			// of current vertex
			int neighbor = edges[current][i];

			// If not present
			// in any of the set
			if (sets[0].count(neighbor) == 0
				&& sets[1].count(neighbor) == 0) {

				// Inserting in opposite
				// of current vertex
				sets[1 - currentSet].insert(neighbor);
				pending.push_back(neighbor);
			}

			// Else if present in the same
			// current vertex set the partition
			// is not possible
			else if (sets[currentSet].count(neighbor)
					> 0) {
				return false;
			}
		}
	}

	return true;
}

bool possibleBipartition(int V,
						vector<vector<int> >& G)
{

	// To store graph as adjacency list in edges
	vector<vector<int> > edges(V + 1);
	for (auto v : G) {
		edges[v[0]].push_back(v[1]);
		edges[v[1]].push_back(v[0]);
	}

	vector<bool> visited(V + 1, false);
	bool res = true;
	for (int i = 1; i <= V; i++) {
		if (!visited[i]) {
			res = res and bipartite(edges, V,
									i, visited);
		}
	}
	return res;
}

int main()
{
	int V, E;
	cin >> V >> E;
	vector<vector<int>> G(E);
	
    for (int i = 0; i < E; i++) {
        int n, m;
        cin >> n >> m;
        G[i].push_back(n);
        G[i].push_back(m);
    }
	// If partition is possible
	if (possibleBipartition(V, G)) {
		//for (auto elem : sets[0]) {
		//	cout << elem << " ";
		//}
		//cout << "\n";
		//for (auto elem : sets[1]) {
		//	cout << elem << " ";
		//}
		for (int i = 1; i<=V; i++){
		    if(sets[0].contains(i)){
		        cout << "1 ";
		    }
		    else {
		        cout << "2 ";
		    }
		}
	}

	// If partition is not possible
	else
		cout << "IMPOSSIBLE";

	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED