Построим граф учеников так, чтобы в одной компоненте связности ученики обязаны были надеть колпак одного цвета.
Сделаем это следующим образом:
- Сопоставим каждому из $$$n \times m$$$ учеников свою вершину в графе.
- Пусть $$$a_1$$$, $$$a_2$$$, ..., $$$a_k$$$ — номера вершин, сопоставленных с учениками одного класса. Проведем следующие ребра: $$$(a_1, a_2)$$$, $$$(a_2, a_3)$$$, ..., $$$(a_{k - 1}, a_k)$$$. Тогда все вершины $$$a_1$$$, $$$a_2$$$, ..., $$$a_k$$$ окажутся в одной компоненте связности.
- Проведем ребра из ученика на позиции $$$(i, j)$$$ в ученика на позиции $$$(i + 1, j)$$$ для всех допустимых $$$i$$$, $$$j$$$. Таким образом ученики из одного столбца окажутся в одной компоненте связности.
В таком графе $$$\mathcal{O}(n \times m)$$$ вершин и ребер. Ответом на задачу будет являться количество компонент связности в таком графе, что можно вычислить с помощью обхода в глубину или обхода в ширину. https://ru.wikipedia.org/wiki/Компонента_связности_графа
Итоговое время работы $$$\mathcal{O}(n \times m)$$$