Building Teams

There are n pupils in Uolevi's class and m friendships between them. Your task is to divide the pupils into two teams in such a way that no two pupils in a team are friends. You can freely choose the sizes of the teams.

Example:

Input: n = 5, m = 3, edges = {{1, 2}, {1, 3}, {4, 5}}
Output: 1 2 2 1 2 

Approach

C++

#include <bits/stdc++.h>
using namespace std;
vector<int> arr[1000001];

void buildingTeams(int n, int m,
                   vector<vector<int>> &edges)
{
    for (int i = 0; i < m; i++)
    {
        int a = edges[i][0], b = edges[i][1];

        arr[a].push_back(b);
        arr[b].push_back(a);
    }
    vector<int> side(n + 1, -1);
    bool is_bipartite = true;
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        if (side[i] == -1)
        {
            q.push(i);
            side[i] = 0;
            while (!q.empty())
            {
                int curr = q.front();
                q.pop();
                for (int child : arr[curr])
                {
                    if (side[child] == -1)
                    {
                        side[child] = side[curr] ^ 1;
                        q.push(child);
                    }
                    else
                        is_bipartite &= side[child] !=
                                        side[curr];
                }
            }
        }
    }
    if (is_bipartite == true)
    {
        for (int i = 1; i <= n; i++)
            cout << side[i] + 1 << " ";
    }
    else
    {
        cout << "IMPOSSIBLE\n";
    }
}
int main()
{
    int n = 5, m = 3;
    vector<vector<int>> edges = {{1, 2}, {1, 3}, {4, 5}};

    buildingTeams(n, m, edges);
    return 0;
}