Divisez les nœuds en un nombre maximum de groupes

2493. Divisez les nœuds en le nombre maximum de groupes

Difficulté: dur

Sujets: Recherche de largeur de largeur, Union Find, graphique

On vous donne un entier positif n représentant le nombre de nœuds dans un graphique non dirigé . Les nœuds sont étiquetés de 1 à n.

Vous avez également des bords de tableau entier 2D, où les bords [i] = [a _i , b _i ] indiquent qu'il y a un bidirectionnel bord entre les nœuds a _i et b _i . AVIS que le graphique donné peut être déconnecté.

Divisez les nœuds du graphique en groupes M ( 1 indexé ) de sorte que:

• Chaque nœud du graphique appartient exactement à un groupe.
• pour chaque paire de nœuds du graphique qui sont connectés par un bord [a _i , b _i ], si a _i appartient au groupe avec l'index x, et b _i appartient au groupe avec l'index y, alors | y - x | = 1.

Retour Le nombre maximum de groupes (c'est-à-dire maximum m) dans lequel vous pouvez diviser les nœuds . Retourner -1 s'il est impossible de regrouper les nœuds avec les conditions données .

Exemple 1:

• Entrée: n = 6, bords = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6] ]
• Sortie: 4
• Explication: Comme indiqué dans l'image, nous:
  • Ajouter le nœud 5 au premier groupe.
  • Ajouter le nœud 1 au deuxième groupe.
  • Ajouter des nœuds 2 et 4 au troisième groupe.
  • Ajouter des nœuds 3 et 6 au quatrième groupe.
  • Nous pouvons voir que chaque bord est satisfait.
  • Il peut être démontré que si nous créons un cinquième groupe et déplaçons n'importe quel nœud du troisième ou quatrième groupe, au moins sur les bords ne sera pas satisfait.

Exemple 2:

• Entrée: n = 3, bords = [[1,2], [2,3], [3,1]]
• sortie: -1
• Explication: Si nous ajoutons le nœud 1 au premier groupe, nœud 2 au deuxième groupe et nœud 3 au troisième groupe pour satisfaire les deux premiers bords, nous pouvons voir que le troisième bord ne sera pas satisfait .
  • Il peut être démontré qu'aucun regroupement n'est possible.

Contraintes:

• 1 & lt; = n & lt; = 500
• 1 & lt; = edges.length & lt; = 10 ⁴
• bords [i] .length == 2
• 1 & lt; = a _i , b _i & lt; = n
• a _i ! = B _i
• Il y a au plus un bord entre n'importe quelle paire de sommets.

Indice:

1. Si le graphique n'est pas bipartite, il n'est pas possible de regrouper les nœuds.
2. Notez que nous pouvons résoudre le problème de chaque composant connecté indépendamment, et la réponse finale ne sera que la somme du nombre maximum de groupes dans chaque composant.
3. Enfin, pour résoudre le problème pour chaque composant connecté, nous pouvons remarquer que si pour un nœud v, nous réparons sa position dans le groupe le plus à gauche, nous pouvons également évaluer la position de tous les autres nœuds. Cette position est la profondeur du nœud dans un arbre BFS après enraciné au nœud v.

Solution:

Le problème, "Divisez les nœuds en le nombre maximum de groupes" , implique de déterminer le nombre maximal de groupes dans lesquels les nœuds d'un graphique non dirigé peuvent être divisés, tels que:

1. Chaque nœud appartient à exactement un groupe.
2. Les nœuds adjacents sont en groupes dont les indices diffèrent exactement 1. Si le graphique n'est pas bipartite, le regroupement est impossible et que la fonction doit retourner -1.

points clés

• Propriétés du graphique: Le graphique peut être déconnecté.
• Validation: Pour chaque composant connecté, vérifiez s'il est bipartite. Sinon, retourz -1.
• Nature bipartite: La solution implique des BF pour valider la bipartité.
• Union-Find: utile pour regrouper efficacement les composants connectés.

Approche

1. Prétraitement:

   • représente le graphique à l'aide d'une liste d'adjacence.
   • Utiliser la recherche d'union pour identifier les composants connectés.

2. BFS pour valider la bipartité:

   • Pour chaque composant connecté, utilisez BFS pour déterminer s'il est bipartite.
   • s'il n'est pas bipartite, retournez -1.

3. Calculer le nombre de groupes:

   • Pour chaque composant connecté, utilisez BFS pour déterminer la profondeur maximale, représentant le nombre maximum de groupes.

4. combiner les résultats:

   • résume le nombre maximal de groupes de tous les composants bipartites.

plan

1. Construisez le graphique comme une liste d'adjacence.
2. Utiliser la recherche d'union pour regrouper les composants connectés.
3. pour chaque nœud du graphique:
   • Utilisez BFS pour vérifier si le graphique est bipartite et calculer la profondeur maximale de ce composant.
4. Renvoyez la somme des profondeurs de tous les composants en conséquence. Si un composant n'est pas bipartite, retournez -1.

implémentons cette solution dans PHP: 2493. Divisez les nœuds en le nombre maximum de groupes

<?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
?>

Explication:

1. Classe-Find Union

Les groupes de structure Union-Find (Disjoint Set Union) sont des nœuds dans des composants connectés et effectuent deux tâches principales:

• trouver: Identifiez la racine du composant connecté d'un nœud.
• Union: fusionner deux composants connectés basés sur le rang.

2. BFS pour la vérification bipartite et le calcul de la profondeur

• Validation bipartite: À l'aide de BFS, attribuez des "couleurs" en alternance aux nœuds. Si les nœuds adjacents partagent la même couleur, le graphique n'est pas bipartite.
• Calcul de profondeur: Mesurez la profondeur de l'arbre BFS pour déterminer le nombre maximum de groupes.

3. Combiner les résultats

• Calculez la profondeur maximale pour chaque composant connecté.
• Ajoutez les profondeurs de tous les composants pour déterminer le résultat.

Exemple de procédure pas à pas

Exemple 1

Entrée:

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

étapes:

1. Construire la liste d'adjacence:

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

1. Utilisez des BF sur les composants connectés:
   • Composant 1: bipartite. Profondeur max = 4.
2. résume les profondeurs sur tous les composants: 4.

Sortie: 4

Exemple 2

Entrée:

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

étapes:

1. Construire la liste d'adjacence:

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

1. Utiliser BFS:
   • Composant 1: pas bipartite.

Sortie: -1

complexité temporelle

• Construction du graphique: o (e) , où e est le nombre de bords.
• Union-Find: o (α (n)) , où n est le nombre de nœuds ( presque constant en raison de la compression du chemin).
• bfs: o (v e) , où v est le nombre de sommets. Complexité globale: o (n e)

Sortie pour les exemples

$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

Cette approche gère efficacement le problème de regroupement en tirant parti de BFS pour les vérifications de la bipartité et les calculs de profondeur tout en utilisant la recherche d'union pour simplifier la gestion des composants. La solution gère les graphiques connectés et déconnectés.

Contact Links

Si vous avez trouvé cette série utile, veuillez envisager de donner le dépositaire une étoile sur GitHub ou de partager le message sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi!

Si vous voulez un contenu plus utile comme celui-ci, n'hésitez pas à me suivre:

• LinkedIn
• github

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!