Nombre maximum de composants K-divisibles

2872. Nombre maximum de composants K-divisibles

Difficulté : Difficile

Sujets : Arbre, recherche en profondeur d'abord

Il existe un arbre non orienté avec n nœuds étiquetés de 0 à n - 1. Vous recevez l'entier n et un tableau d'entiers 2D Edges de longueur n - 1, où Edges[i] = [a_i, b_i] indique qu'il y a une arête entre les nœuds a_i et b_i dans l'arbre.

Vous recevez également un tableau de valeurs entières indexées à 0 de longueur n, où valeurs[i] est la valeur associée au i^ème nœud, et un entier k.

Une division valide de l'arbre est obtenue en supprimant tout ensemble d'arêtes, éventuellement vides, de l'arbre de telle sorte que les composants résultants aient tous des valeurs divisibles par k, où la valeur d'un composant connecté est la somme des valeurs de ses nœuds.

Renvoyer le nombre maximum de composants dans toute répartition valide.

Exemple 1 :

• Entrée : n = 5, bords = [[0,2],[1,2],[1,3],[2,4]], valeurs = [1,8,1,4 ,4], k = 6
• Sortie : 2
• Explication : Nous supprimons le nœud de connexion de bord 1 avec 2. La division résultante est valide car :
  • La valeur du composant contenant les nœuds 1 et 3 est valeurs[1] valeurs[3] = 12.
  • La valeur du composant contenant les nœuds 0, 2 et 4 est valeurs[0] valeurs[2] valeurs[4] = 6.
  • On peut montrer qu'aucune autre division valide n'a plus de 2 composants connectés.

Exemple 2 :

• Entrée : n = 7, bords = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6] ], valeurs = [3,0,6,1,5,2,1], k = 3
• Sortie : 3
• Explication : Nous supprimons le nœud de connexion de bord 0 avec 2 et le nœud de connexion de bord 0 avec 1. La division résultante est valide car :
  • La valeur du composant contenant le nœud 0 est valeurs[0] = 3.
  • La valeur du composant contenant les nœuds 2, 5 et 6 est valeurs[2] valeurs[5] valeurs[6] = 9.
  • La valeur du composant contenant les nœuds 1, 3 et 4 est valeurs[1] valeurs[3] valeurs[4] = 6.
  • On peut montrer qu'aucune autre division valide n'a plus de 3 composants connectés.

Contraintes :

• 1 <= n <= 3*10⁴
• edges.length == n - 1
• bords[i].length == 2
• 0 <= ai, bi < n
• values.length == n
• 0 <= valeurs[i] <= 10⁹
• 1 <= k <= 10⁹
• La somme des valeurs est divisible par k.
• L'entrée est générée de telle sorte que les bords représentent un arbre valide.

Indice :

1. Enracinez l'arbre au nœud 0.
2. Si un nœud feuille n'est pas divisible par k, il doit être dans le même composant que son nœud parent donc nous le fusionnons avec son nœud parent.
3. Si un nœud feuille est divisible par k, il le sera dans ses propres composants donc on le sépare de son nœud parent.
4. À chaque étape, soit nous coupons un nœud feuille, soit nous fusionnons un nœud feuille. Le nombre de nœuds sur l'arborescence est réduit de un. Répétez ce processus jusqu'à ce qu'il ne reste qu'un seul nœud.

Solution :

Nous pouvons mettre en œuvre une approche de recherche en profondeur (DFS) pour explorer l'arbre, suivre les valeurs des composants et trouver le nombre maximum de divisions valides.

Points clés :

• Structure arborescente : Nous travaillons avec un arbre non orienté où chaque nœud a une valeur associée. Nous devons trouver le nombre maximum de composants connectés que nous pouvons obtenir en divisant l'arbre de telle sorte que la somme des valeurs de chaque composant soit divisible par k.
• Traversée DFS : Nous utilisons la recherche en profondeur (DFS) pour parcourir l'arbre et calculer les sommes des sous-arbres.
• Vérification de divisibilité : Après avoir calculé la somme d'un sous-arbre, s'il est divisible par k, cela signifie que le sous-arbre peut être considéré comme un composant valide par lui-même.
• Suppression des bords : En supprimant les bords qui connectent les nœuds dont les sommes des sous-arbres ne sont pas divisibles par k, nous pouvons maximiser le nombre de composants valides.

Approche:

1. Représentation de l'arbre : Convertissez la liste des arêtes en une liste de contiguïté pour représenter l'arbre.
2. DFS Traversal : Commencez à partir du nœud 0 et calculez récursivement la somme des valeurs dans chaque sous-arbre. Si la somme est divisible par k, nous pouvons couper ce sous-arbre de son parent, formant ainsi un composant valide.
3. Compte global : Maintenez un compteur global (résultat) qui suit le nombre de composants valides formés par les arêtes de coupe.
4. Vérification finale : À la fin du parcours DFS, assurez-vous que si la somme totale du sous-arbre de la racine est divisible par k, elle compte comme un composant valide.

Plan:

1. Analyse des entrées : Convertissez l'entrée en un formulaire utilisable. Plus précisément, créez une représentation de liste de contiguïté pour l'arborescence.
2. Fonction DFS : Écrivez une fonction récursive dfs(node) qui calcule la somme des valeurs dans le sous-arbre enraciné au nœud. Si cette somme est divisible par k, incrémentez le compteur de résultat et "coupez" le bord en renvoyant 0 pour éviter la fusion dans le parent.
3. Démarrez DFS à partir de Root : Appelez dfs(0), puis vérifiez la valeur finale du résultat.

Étapes de la solution :

1. Construisez l'arborescence : Convertissez la liste de bords en liste de contiguïté pour un parcours plus facile.
2. Initialiser le tableau visité : Utilisez un tableau visité pour vous assurer que nous ne revisitons pas les nœuds.
3. DFS Traversal : Effectuez DFS à partir du nœud 0. Pour chaque nœud, calculez la somme des valeurs de son sous-arbre.
4. Vérifier la divisibilité : Si la somme d'un sous-arbre est divisible par k, incrémentez le résultat et réinitialisez la somme du sous-arbre à 0.
5. Vérification finale du composant : Après le parcours DFS, vérifiez si l'arbre entier (enraciné au nœud 0) a une somme divisible par k et tenez-en compte comme un composant distinct si nécessaire.

Implémentons cette solution en PHP : 2872. Nombre maximum de composants K-divisibles

  
  
  Explication:




Construction d'arbre : Nous construisons une liste de contiguïté pour représenter la structure arborescente. Chaque arête connecte deux nœuds, et nous utilisons cette liste de contiguïté pour parcourir l'arborescence.

DFS Traversal : La fonction DFS calcule de manière récursive la somme du sous-arbre enraciné à chaque nœud. Si la somme du sous-arbre est divisible par k, nous incrémentons le résultat et considérons le sous-arbre comme un composant valide distinct.

Renvoi de la somme du sous-arbre : Pour chaque nœud, la fonction DFS renvoie la somme des valeurs de son sous-arbre. Si un sous-arbre est divisible par k, nous "coupons" effectivement le bord en renvoyant une somme de 0, empêchant ainsi une nouvelle fusion avec le nœud parent.

Vérification finale : À la fin du DFS, nous nous assurons que si la somme de l'arbre entier est divisible par k, elle compte comme une composante valide.



  
  
  Exemple de procédure pas à pas :


Exemple 1 :

Entrée :



n = 5, bords = [[0,2],[1,2],[1,3],[2,4]], valeurs = [1,8,1,4,4], k = 6. 


DFS démarre à partir du nœud 0 :


Nœud 0 : somme du sous-arbre = 1
Nœud 2 : somme du sous-arbre = 1 1 4 = 6 (divisible par 6, on peut donc couper ce bord)
Nœud 1 : somme du sous-arbre = 8 4 = 12 (divisible par 6, coupez ce bord)
Nombre final de composants = 2.


Exemple 2 :

Entrée :



n = 7, bords = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], valeurs = [3,0 ,6,1,5,2,1], k = 3.


DFS démarre à partir du nœud 0 :


Nœud 0 : somme du sous-arbre = 3
Nœud 2 : somme du sous-arbre = 6 2 1 = 9 (divisible par 3, coupez ce bord)
Nœud 1 : somme du sous-arbre = 0 5 = 5 (non divisible par 3, fusionner cette somme)
Nombre final de composants = 3.



  
  
  Complexité temporelle :




Complexité temporelle DFS : O(n), où n est le nombre de nœuds. Nous visitons chaque nœud une fois et effectuons des opérations à temps constant sur chaque nœud.

Complexité spatiale : O(n) pour la liste de contiguïté, le tableau visité et la pile de récursion.


Ainsi, la complexité temporelle et spatiale globale est O(n), ce qui rend cette approche efficace pour les contraintes de problème données.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du 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!