Todos los desafíos
Intermedio 1 resuelto 100.0% de aceptación

Can We Split Into Two Teams?

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

Lo que aprenderás

  • Modelar personas y conflictos como un grafo
  • Comprobar si es bipartito con dos colores
  • Manejar partes desconectadas de un grafo

Problema

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.

Restricciones

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

Ejemplos

Ejemplo 1
Entrada:
people = 3
pairs = [
    [1, 2],
    [2, 3],
    [3, 1]
]

Salida esperada:
expected = False
Entrada:
long long people = 3;
std::vector<std::vector<long long>> pairs = {
    {1, 2},
    {2, 3},
    {3, 1}
};

Salida esperada:
bool expected = false;
Entrada:
long people = 3;
long[][] pairs = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3},
    new long[] {3, 1}
};

Salida esperada:
bool expected = false;

Explicación

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

Ejemplo 2
Entrada:
people = 4
pairs = [
    [1, 2],
    [2, 3]
]

Salida esperada:
expected = True
Entrada:
long long people = 4;
std::vector<std::vector<long long>> pairs = {
    {1, 2},
    {2, 3}
};

Salida esperada:
bool expected = true;
Entrada:
long people = 4;
long[][] pairs = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3}
};

Salida esperada:
bool expected = true;

Explicación

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

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Esto es posible exactamente cuando cada componente de restricciones se puede colorear con dos colores distintos.

Pista 2

Recorre cada componente conexa y alterna la asignación de equipos en cada restricción por parejas.

Pista 3

Si alguna vez necesitas dar a la misma persona ambos equipos por un ciclo impar, la respuesta pasa a ser false.

Complejidad esperada

tiempo O(people + pairs), espacio extra O(people + pairs)

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

# Programador Lenguaje Tiempo Memoria Revisión de IA Solución
1 ННикита Python 797 ms - 5/5 Ver código

Aprende de otros

Soluciones de la comunidad

Alerta de spoiler: 1 solución completa abajo Intenta resolverlo tú mismo primero. Igual puedes ver el código de otros desarrolladores y las reseñas de IA. Inicia sesión y resuelve el reto para unirte a la discusión.