Tutte le sfide
Media 1 risolta 100.0% di accettazione

Can We Split Into Two Teams?

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

Cosa imparerai

  • Modellare persone e conflitti come un grafo
  • Verificare la bipartizione con due colori
  • Gestire le parti non connesse di 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.

Vincoli

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

Esempi

Esempio 1
Input:
people = 3
pairs = [
    [1, 2],
    [2, 3],
    [3, 1]
]

Output atteso:
expected = False
Input:
long long people = 3;
std::vector<std::vector<long long>> pairs = {
    {1, 2},
    {2, 3},
    {3, 1}
};

Output atteso:
bool expected = false;
Input:
long people = 3;
long[][] pairs = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3},
    new long[] {3, 1}
};

Output atteso:
bool expected = false;

Spiegazione

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

Esempio 2
Input:
people = 4
pairs = [
    [1, 2],
    [2, 3]
]

Output atteso:
expected = True
Input:
long long people = 4;
std::vector<std::vector<long long>> pairs = {
    {1, 2},
    {2, 3}
};

Output atteso:
bool expected = true;
Input:
long people = 4;
long[][] pairs = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3}
};

Output atteso:
bool expected = true;

Spiegazione

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

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

È possibile esattamente quando ogni componente di vincoli può essere colorata con due colori diversi.

Suggerimento 2

Attraversa ogni componente connessa e alterna l’assegnazione ai due team su ogni vincolo di coppia.

Suggerimento 3

Se per un ciclo dispari devi assegnare la stessa persona a entrambi i team, la risposta diventa false.

Complessità attesa

tempo O(people + pairs), spazio aggiuntivo O(people + pairs)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

# Programmatore Linguaggio Tempo Memoria Voto dell'IA Soluzione
1 ННикита Python 797 ms - 5/5 Vedi il codice

Impara dagli altri

Soluzioni della community

Attenzione spoiler: 1 soluzione completa sotto Prova prima a risolverla da solo. Puoi comunque sbirciare il codice degli altri sviluppatori e le recensioni AI. Accedi e risolvi la sfida per partecipare alla discussione.