Логотип YeaHub
Войти
Назад

Списывание (Cheating Groups)

3

GoJavaJavaScriptPython

Графы

Яндекс

Условие:

Во время контрольной работы профессор заметил обмен записками между некоторыми студентами. Он хочет разделить всех студентов на две группы так, чтобы любой обмен записками происходил только между студентами из разных групп (то есть внутри одной группы обменов быть не должно).

Дано количество студентов и список пар студентов, обменивавшихся записками. Необходимо определить, возможно ли такое разделение.

Входные данные:

  • n — количество студентов (1 ≤ n ≤ 100), пронумерованы от 1 до n

  • pairs — массив пар чисел [a, b], каждая пара — обмен записками между студентами a и b (каждая пара встречается не более одного раза, без пар вида [a, a])

Выходные данные:
Булево значение: true, если разделение на две группы возможно, false — если нет.

Ограничения:

  • 1 ≤ n ≤ 100

  • 0 ≤ количество пар ≤ n(n-1)/2

Пример:

Вход: n=4, pairs=[[1,2],[2,3],[3,4]]
Выход: true

Вход: n=3, pairs=[[1,2],[2,3],[1,3]]
Выход: false
Loading...