Building Teams

input/code.cpp: In function 'bool bfs(int, std::vector<Pupil>&)':
input/code.cpp:22:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |        for (int f_id = 0; f_id < pupils[p].friends.size(); f_id++)
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Pupil>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i = 0; i < pupils.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
input/code.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Pupil>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i = 0; i < pupils.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~

#include <iostream>
#include <vector>
#include <queue>


struct Pupil
{
    int team = 0;
    std::vector<int> friends;
};

bool bfs(int pupil, std::vector<Pupil>& pupils)
{
    std::queue<int> q;
    q.push(pupil);
    pupils[pupil].team = 1; 
    while (q.size())
    {
       int p = q.front();
       q.pop();
       
       for (int f_id = 0; f_id < pupils[p].friends.size(); f_id++)
       {
           if (pupils[pupils[p].friends[f_id]].team == pupils[p].team)
               return true;
           if (pupils[pupils[p].friends[f_id]].team != 0)
               continue;
           
            q.push(pupils[p].friends[f_id]);
            if (pupils[p].team == 1)
                pupils[pupils[p].friends[f_id]].team = 2;
            else
                pupils[pupils[p].friends[f_id]].team = 1;
            
       }
    }

    return false;
}

int main()
{
    int n, m;

    std::cin >> n >> m;    
    std::vector<Pupil> pupils; 
    
    for (int i = 0; i < n; i++)
    {
        pupils.push_back(Pupil());
    }

    for (int i = 0; i < m; i++)
    {
        int a, b;
        std::cin >> a >> b;
        pupils[a - 1].friends.push_back(b - 1);
        pupils[b - 1].friends.push_back(a - 1);
    }
    
    for (int i = 0; i < pupils.size(); i++)
    {
        if (pupils[i].team) continue;
        if (bfs(i, pupils))
        {
            std::cout << "IMPOSSIBLE\n";
            return 0;
        }

            
    }
    for (int i = 0; i < pupils.size(); i++)
    {
        std::cout << pupils[i].team << " ";
    }
    std::cout << "\n";
    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