Все задачи
Средне Решена: 1 Процент решений: 100.0%

Can We Split Into Two Teams?

Decide whether people can be assigned to two teams so that each listed pair is on opposite teams.

Чему вы научитесь

  • Моделировать людей и конфликты графом
  • Проверять двудольность двумя цветами
  • Обрабатывать несвязные части графа

Условие

Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. Every person receives exactly one team; either team may be empty. People without a listed pair can go on either team. Check every connected group of constraints.

Implement split_into_two_teams(people, pairs).

Input

people: The number of people, numbered from 1.

pairs: Rows [first_person, second_person] that must be separated.

Output

Return true if any valid assignment exists, otherwise false. Do not return the assignment.

Ограничения

1 ≤ people ≤ 100,000. 0…200,000 pairs of distinct person IDs in 1…people. Duplicate pairs are allowed and repeat the same constraint.

Примеры

Пример 1
Ввод:
people = 3
pairs = [
    [1, 2],
    [2, 3],
    [3, 1]
]

Ожидаемый вывод:
expected = False
Ввод:
long long people = 3;
std::vector<std::vector<long long>> pairs = {
    {1, 2},
    {2, 3},
    {3, 1}
};

Ожидаемый вывод:
bool expected = false;
Ввод:
long people = 3;
long[][] pairs = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3},
    new long[] {3, 1}
};

Ожидаемый вывод:
bool expected = false;

Пояснение

If 1 is on team A, 2 must be on B, and 3 must be on A. The last pair then violates the rule.

Пример 2
Ввод:
people = 4
pairs = [
    [1, 2],
    [2, 3]
]

Ожидаемый вывод:
expected = True
Ввод:
long long people = 4;
std::vector<std::vector<long long>> pairs = {
    {1, 2},
    {2, 3}
};

Ожидаемый вывод:
bool expected = true;
Ввод:
long people = 4;
long[][] pairs = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3}
};

Ожидаемый вывод:
bool expected = true;

Пояснение

Put 1 and 3 on team A and 2 on team B. Person 4 can join either team.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Это возможно тогда и только тогда, когда каждую связанную по ограничениям компоненту можно раскрасить в два цвета.

Подсказка 2

Обходи каждую connected component и чередуй назначение команд на каждой паре ограничений.

Подсказка 3

Если из-за нечётного цикла приходится отдать одному человеку обе команды, ответ становится false.

Ожидаемая сложность

время O(people + pairs), доп. память O(people + pairs)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

# Участник Язык Время Память Оценка ИИ Решение
1 ННикита Python 797 ms - 5/5 Посмотреть код

Учитесь у других

Решения сообщества

Внимание, спойлер: ниже 1 полное решение Попробуйте сначала решить сами. Вы всегда можете посмотреть код других и AI-обзоры. Войдите и решите задание, чтобы присоединиться к обсуждению.