Alle Herausforderungen
Mittel 1 gelöst 100.0% Erfolgsquote

Can We Split Into Two Teams?

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

Das lernst du

  • Personen und Konflikte als Graph modellieren
  • Bipartitheit mit zwei Farben prüfen
  • Nicht zusammenhängende Teile eines Graphen behandeln

Problem

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.

Einschränkungen

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

Beispiele

Beispiel 1
Eingabe:
people = 3
pairs = [
    [1, 2],
    [2, 3],
    [3, 1]
]

Erwartete Ausgabe:
expected = False
Eingabe:
long long people = 3;
std::vector<std::vector<long long>> pairs = {
    {1, 2},
    {2, 3},
    {3, 1}
};

Erwartete Ausgabe:
bool expected = false;
Eingabe:
long people = 3;
long[][] pairs = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3},
    new long[] {3, 1}
};

Erwartete Ausgabe:
bool expected = false;

Erläuterung

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

Beispiel 2
Eingabe:
people = 4
pairs = [
    [1, 2],
    [2, 3]
]

Erwartete Ausgabe:
expected = True
Eingabe:
long long people = 4;
std::vector<std::vector<long long>> pairs = {
    {1, 2},
    {2, 3}
};

Erwartete Ausgabe:
bool expected = true;
Eingabe:
long people = 4;
long[][] pairs = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3}
};

Erwartete Ausgabe:
bool expected = true;

Erläuterung

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

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Das ist genau dann möglich, wenn jede Zusammenhangskomponente mit zwei verschiedenen Farben gefärbt werden kann.

Hinweis 2

Durchlaufe jede zusammenhängende Komponente und wechsle die Teamzuweisung entlang jeder Paar-Constraint.

Hinweis 3

Wenn du wegen eines ungeraden Zyklus jemandem beide Teams geben müsstest, wird das Ergebnis false.

Erwartete Komplexität

Zeit O(people + pairs), zusätzlicher Speicher O(people + pairs)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 797 ms - 5/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.