Tous les défis
Moyen 1 résolu 100.0 % de réussite

Can We Split Into Two Teams?

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

Ce que vous allez apprendre

  • Modéliser les personnes et les conflits par un graphe
  • Vérifier la bipartition avec deux couleurs
  • Gérer les parties non connexes d'un graphe

Problème

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.

Contraintes

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

Exemples

Exemple 1
Entrée :
people = 3
pairs = [
    [1, 2],
    [2, 3],
    [3, 1]
]

Sortie attendue :
expected = False
Entrée :
long long people = 3;
std::vector<std::vector<long long>> pairs = {
    {1, 2},
    {2, 3},
    {3, 1}
};

Sortie attendue :
bool expected = false;
Entrée :
long people = 3;
long[][] pairs = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3},
    new long[] {3, 1}
};

Sortie attendue :
bool expected = false;

Explication

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

Exemple 2
Entrée :
people = 4
pairs = [
    [1, 2],
    [2, 3]
]

Sortie attendue :
expected = True
Entrée :
long long people = 4;
std::vector<std::vector<long long>> pairs = {
    {1, 2},
    {2, 3}
};

Sortie attendue :
bool expected = true;
Entrée :
long people = 4;
long[][] pairs = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3}
};

Sortie attendue :
bool expected = true;

Explication

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

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

C’est possible exactement quand chaque composant de contrainte peut être coloré avec deux couleurs différentes.

Indice 2

Parcourez chaque composant connexe et alternez les affectations d’équipe sur chaque paire de contrainte.

Indice 3

Si vous devez donner à une même personne les deux équipes à cause d’un cycle impair, la réponse devient false.

Complexité attendue

temps O(people + pairs), espace supplémentaire O(people + pairs)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 797 ms - 5/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.