Teilen Sie Knoten in die maximale Anzahl von Gruppen ein

2493. Teilen Sie Knoten in die maximale Anzahl von Gruppen

auf

Schwierigkeitsgrad: Hard

Themen: Breite zuerst Search, Union Find, Graph

Sie erhalten eine positive Ganzzahl n, die die Anzahl der Knoten in einem ungerichteten -Angraßen darstellt. Die Knoten sind von 1 bis n. gekennzeichnet

Sie erhalten auch eine 2D -Ganzzahl -Array -Kanten, an der Kanten [i] = [A

i _{, b} i _{] angeben, dass es ein} bidirectional gibt Kante zwischen den Knoten A i _{und b} i _. Beachten Sie , dass der angegebene Diagramm getrennt werden kann.

Teilen Sie die Knoten des Diagramms in M-Gruppen (

1-iNDEXED ), so dass:

Jeder Knoten im Diagramm gehört genau einer Gruppe.
für jedes Knotenpaar in der Grafik, die durch eine Kante verbunden sind [a
• i _{, b} i _{], wenn a} i _{zur Gruppe gehört mit Index x und b} i _{gehört zur Gruppe mit Index y, dann | y - x | = 1.}

return

Die maximale Anzahl von Gruppen (d. H. Maximal m), in die Sie die Knoten teilen können. Return -1, wenn es unmöglich ist, die Knoten mit den angegebenen Bedingungen zu gruppieren .

Beispiel 1:

• Eingabe: n = 6, Kanten = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6] ]
• Ausgabe: 4
• Erläuterung: Wie im Bild gezeigt wir:
  Node 5 zur ersten Gruppe hinzufügen.
  Node 1 zur zweiten Gruppe hinzufügen.
  Fügen Sie die Knoten 2 und 4 zur dritten Gruppe hinzu.
  Fügen Sie die Knoten 3 und 6 in die vierte Gruppe hinzu.
  Wir können sehen, dass jede Kante zufrieden ist.
  Es kann gezeigt werden, dass, wenn wir eine fünfte Gruppe erstellen und einen Knoten von der dritten oder vierten Gruppe auf sie verschieben, zumindest an den Kanten nicht erfüllt sein wird.

Beispiel 2:

• Eingabe: n = 3, Kanten = [1,2], [2,3], [3,1]]
• Ausgabe: -1
• Erläuterung: Wenn wir der ersten Gruppe den Knoten 1 zur zweiten Gruppe und den Knoten 3 zur dritten Gruppe hinzufügen, um die ersten beiden Kanten zu erfüllen .
  Es kann gezeigt werden, dass keine Gruppierung möglich ist.

Einschränkungen:

1 & lt; = n & lt; = 500
1 & lt; = Kanten.Length & lt; = 10
• 4
Kanten [i] .Length == 2
1 & lt; = a
• i _{, b} i _{& lt;} a
i
• ! = B _i Es gibt höchstens eine Kante zwischen jedem Eckpaar.

Hinweis:

1. Wenn das Diagramm nicht zweipartner ist, ist es nicht möglich, die Knoten zu gruppieren.
2. Beachten Sie, dass wir das Problem für jede angeschlossene Komponente unabhängig lösen können, und die endgültige Antwort ist nur die Summe der maximalen Anzahl von Gruppen in jeder Komponente.
3. Um das Problem für jede angeschlossene Komponente zu lösen, können wir feststellen, dass wir für einen Knoten V seine Position in der Gruppe links festlegen können, die wir auch die Position jedes anderen Knotens bewerten können. Diese Position ist die Tiefe des Knotens in einem BFS -Baum nach dem Wurzeln am Knoten v.

Lösung:

Das Problem, "Teilen Knoten in die maximale Anzahl von Gruppen" beinhaltet die Bestimmung der maximalen Anzahl von Gruppen, in die die Knoten eines ungerichteten Graphen unterteilt werden können, so dass:

1. Jeder Knoten gehört genau einer Gruppe.
2. benachbarte Knoten befinden sich in Gruppen, deren Indizes genau 1 unterscheiden. Wenn das Diagramm nicht zweipartner ist, ist die Gruppierung unmöglich und die Funktion muss -1 zurückgeben.

Schlüsselpunkte

• Grapheigenschaften: Der Diagramm kann getrennt werden.
• Validierung: Überprüfen Sie für jede angeschlossene Komponente, ob es sich um zweigliedrig handelt. Wenn nicht, geben Sie -1 zurück
• bipartitale Natur: Die Lösung beinhaltet BFS zur Validierung von zweiteilig.
• Union-Find: nützlich für die effiziente Gruppierung verbundener Komponenten.

Ansatz

1. Vorverarbeitung:

   • stellen das Diagramm mit einer Adjazenzliste dar.
   • Verwenden Sie Union-Find, um verbundene Komponenten zu identifizieren.

2. BFS zur Validierung der zweifeiligen Kräfte:

   • Verwenden Sie für jede angeschlossene Komponente BFS, um zu bestimmen, ob es sich um zweipartner gestaltet.
   • Wenn es nicht zweigliedrig ist, return -1.

3. Gruppenzahl berechnen:

   • Verwenden Sie für jede angeschlossene Komponente BFS, um die maximale Tiefe zu bestimmen, die die maximale Anzahl von Gruppen darstellt.

4. Ergebnisse kombinieren:

   • Summe die maximalen Gruppenzahlen aller zweigliedrigen Komponenten.

Plan

1. Konstruieren Sie das Diagramm als Adjazenzliste.
2. UNION-FIND mit Gruppenanschließungskomponenten verwenden.
3. für jeden Knoten im Diagramm:
   • Verwenden Sie BFS, um zu überprüfen, ob das Diagramm zweipartner ist, und berechnen Sie die maximale Tiefe dieser Komponente.
4. Geben Sie die Summe der Tiefen aller Komponenten als Ergebnis zurück. Wenn eine Komponente nicht zweipartner ist, geben Sie -1 zurück

implementieren wir diese Lösung in PHP: 2493. Teilen Sie Knoten in die maximale Anzahl von Gruppen

<?php /**
 * @param Integer $n
 * @param Integer[][] $edges
 * @return Integer
 */
function magnificentSets($n, $edges) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $graph
 * @param $u
 * @return int
 */
private function bfs($graph, $u) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

class UnionFind {
    /**
     * @var array
     */
    private $id;
    /**
     * @var array
     */
    private $rank;

    /**
     * @param $n
     */
    public function __construct($n) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $u
     * @param $v
     * @return void
     */
    public function unionByRank($u, $v) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $u
     * @return mixed
     */
    public function find($u) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}


// Example usage:
$n = 6;
$edges = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6]];
echo maxGroups($n, $edges); // Output: 4

$n = 3;
$edges = [[1,2], [2,3], [3,1]];
echo maxGroups($n, $edges); // Output: -1
?>

Erläuterung:

1. Union-Find-Klasse

Die Struktur der Union-Find (Disjoint-Set-Set) gruppiert Knoten in verbundenen Komponenten und führt zwei Hauptaufgaben aus:

• Finden Sie: Identifizieren Sie das Wurzel der angeschlossenen Komponente eines Knotens.
• Union: Zusammenführen zwei verbundene Komponenten basierend auf Rang.

2. BFS für die partitale Überprüfung und Tiefenberechnung

• Bipartitenvalidierung: Verwenden von BFS wechseln Sie Knoten abwechselnd "Farben". Wenn benachbarte Knoten dieselbe Farbe haben, ist der Diagramm nicht zweipartner.
• Tiefe Berechnung: Messen Sie die Tiefe des BFS -Baums, um die maximale Anzahl von Gruppen zu bestimmen.

3. Kombinieren Sie Ergebnisse

• Berechnen Sie die maximale Tiefe für jede angeschlossene Komponente.
• Fügen Sie die Tiefen für alle Komponenten hinzu, um das Ergebnis zu bestimmen.

Beispiel Walkthrough

Beispiel 1

Eingabe:

$n = 6;  
$edges = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6]];

Schritte:

1. Konstrukt -Adjazenzliste:

   1 -> [2, 4, 5]
   2 -> [1, 3, 6]
   3 -> [2]
   4 -> [1, 6]
   5 -> [1]
   6 -> [2, 4]

1. Verwenden Sie BFS für angeschlossene Komponenten:
   • Komponente 1: zweipartneres. Maximale Tiefe = 4.
2. Summe Tiefe über alle Komponenten hinweg: 4.

Ausgabe: 4

Beispiel 2

Eingabe:

$n = 3;  
$edges = [[1,2], [2,3], [3,1]];

Schritte:

1. Konstrukt -Adjazenzliste:

   1 -> [2, 3]
   2 -> [1, 3]
   3 -> [1, 2]

1. Verwenden Sie BFS:
   • Komponente 1: nicht zweipartner.

Ausgabe: -1

Zeitkomplexität

• Graph Construction: o (e) , wobei e die Anzahl der Kanten ist.
• Union-Find: o (α (n)) , wobei n die Anzahl der Knoten ist (Knoten ( fast konstant aufgrund der Pfadkompression).
• bfs: o (v e) , wobei v die Anzahl der Eckpunkte ist. Gesamtkomplexität: o (n e)

Ausgabe für Beispiele

$n = 6;
$edges = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6]];
echo magnificentSets($n, $edges); // Output: 4

$n = 3;
$edges = [[1,2], [2,3], [3,1]];
echo magnificentSets($n, $edges); // Output: -1

Dieser Ansatz behandelt das Gruppierungsproblem effizient, indem BFS für zweifache Überprüfungen und Tiefenberechnungen eingesetzt wird und gleichzeitig Union-Find verwendet wird, um das Komponentenmanagement zu vereinfachen. Die Lösung behandelt sowohl verbundene als auch getrennte Grafiken.

Kontaktlinks

Wenn Sie diese Serie hilfreich gefunden haben, sollten Sie das repository einen Stern auf GitHub geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken teilen? Ihre Unterstützung würde mir viel bedeuten!

Wenn Sie mehr hilfreiche Inhalte wie diesen wünschen, können Sie mir gerne folgen:

• linkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonTeilen Sie Knoten in die maximale Anzahl von Gruppen ein. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!