eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Долой списывание!

опубликовано 31.03.2023, 16:16:11

The idea is to use a variation of depth-first search to check if the graph of students and exchange of notes can be divided into two groups. We represent the graph using an adjacency list. Each node (student) is initially uncolored. We perform a depth-first search starting from each uncolored node. When visiting a node, we assign it a color (1 or -1), and we recursively visit all its neighbors, assigning them the opposite color. If we find a neighbor that has the same color as the current node, then we know that the graph cannot be divided into two groups, and we can return false. Otherwise, if we have visited all nodes without finding a conflict, then the graph is bipartite, and we can return true.