Урок физкультуры

Построим граф учеников так, чтобы в одной компоненте связности ученики обязаны были надеть колпак одного цвета.

Сделаем это следующим образом:

В таком графе $$$\mathcal{O}(n \times m)$$$ вершин и ребер. Ответом на задачу будет являться количество компонент связности в таком графе, что можно вычислить с помощью обхода в глубину или обхода в ширину. https://ru.wikipedia.org/wiki/Компонента_связности_графа

Итоговое время работы $$$\mathcal{O}(n \times m)$$$