


Interroger le nombre de composants connectés après avoir supprimé un sommet de l'arborescence
La requête suivante peut être utilisée pour déterminer les composants connectés restants après la suppression des sommets de l'arborescence : Considérez d'abord la structure arborescente. Ensuite, chaque composant connecté est examiné en se déplaçant dans l’arborescence à l’aide d’un algorithme de recherche en largeur ou en profondeur. Une fois les sommets requis supprimés, la même méthode de parcours est utilisée pour décider du nombre de composants connectés. Le résultat sera déterminé en fonction de l'évolution des décomptes avant et après l'expulsion. Cette méthode surveille efficacement les modifications de connexion et facilite le calcul des mises à jour des composants connectés dans l'arborescence.
Méthode à utiliser
Méthode de recherche en profondeur (DFS)
Et vérifiez la méthode
Méthode de recherche en profondeur (DFS)
Dans la méthode DFS, nous effectuons d'abord un parcours DFS à partir de n'importe quel nœud sélectionné dans l'arborescence d'origine pour compter les composants connectés après avoir supprimé les sommets de l'arborescence. Au cours de ce parcours, nous parcourons chaque nœud connecté, marquons chaque nœud comme visité et suivons le nombre de fois que DFS a été utilisé. Nous effectuons un nouveau parcours DFS après la suppression d'un sommet spécifié, garantissant que les sommets supprimés sont ignorés pendant la phase d'exploration. Nous pouvons déterminer le nombre de composants connectés dans l'arborescence mise à jour en comparant le nombre d'appels à DFS avant et après la suppression. Cette méthode peut compter efficacement le nombre d’éléments connectés tout en s’adaptant aux changements dans la structure arborescente.
Algorithme
Sélectionnez n'importe quel sommet de l'arbre d'origine comme point de départ du parcours DFS.
Définissez la variable "count" pour commencer à compter les composants connectés. Tout d’abord, réglez-le sur 0.
À partir du sommet de départ sélectionné, utilisez DFS pour parcourir l'arbre.
Marquez chaque sommet visité lors du parcours DFS et incrémentez le "compte" de 1 pour chaque nouvel appel DFS (c'est-à-dire pour chaque composant connecté trouvé).
Une fois le parcours DFS terminé, le nombre d'éléments connectés dans l'arborescence d'origine sera représenté par "count".
Supprimez le sommet spécifié de l'arbre.
Répétez le parcours DFS à partir du même sommet de départ, en veillant à éviter d'explorer les sommets supprimés.
Lors de l'exécution de DFS, mettez à jour la variable "count" de la même manière qu'auparavant.
Le nombre de composants associés dans l'arborescence mise à niveau sera déterminé en soustrayant le « compte » post-évacuation du « compte » de départ.
Exemple
#include <iostream> #include <vector> void dfs(const std::vector<std::vector<int>>& tree, int v, std::vector<bool>& visited, int& count) { visited[v] = true; count++; for (int u : tree[v]) { if (!visited[u]) { dfs(tree, u, visited, count); } } } int countConnectedComponents(const std::vector<std::vector<int>>& tree, int startVertex) { int n = tree.size(); std::vector<bool> visited(n, false); int count = 0; dfs(tree, startVertex, visited, count); return count; } int main() { std::vector<std::vector<int>> tree = { {1, 2}, {0, 3}, {0, 4}, {1}, {2} }; int startVertex = 0; std::cout << countConnectedComponents(tree, startVertex) << std::endl; return 0; }
Sortie
5
Et vérifiez la méthode
Nous initialisons d'abord chaque sommet en tant que composant distinct dans la méthode de recherche d'union afin de pouvoir compter les composants connectés après avoir supprimé le sommet de l'arbre. Pour garder une trace des pièces et des connexions dans l'arborescence d'origine, nous prenons et recherchons des structures de données. Nous mettons à jour et interrogeons la structure des données pour refléter le changement dans la connectivité de l'arborescence après la suppression du sommet spécifié. Comptez et vérifiez ensuite le nombre d’ensembles différents dans la structure de données. Le nombre résultant représente la connectivité des composants mis à jour de l'arborescence. Après avoir supprimé les sommets, la méthode de recherche peut calculer efficacement les composants connectés et gérer efficacement les changements structurels dans l'arborescence.
Algorithme
Créez un tableau ou une structure de données à partir de zéro pour représenter chaque sommet comme une partie différente de l'arbre. Initialement, chaque sommet est son propre sommet parent.
Utilisez l'opération de recherche AND dans l'étape de prétraitement pour déterminer le nombre de composants connectés de l'arborescence d'origine.
Utilisez la structure de données union pour combiner les parties de l'arbre qui contiennent les sommets u et v pour chaque arête (u, v). La connectivité initiale de l'arborescence est établie dans cette étape.
Supprimez le sommet spécifié de l'arbre.
Appliquez l'opération de recherche d'union de l'étape de prétraitement à l'arbre modifié.
Après la suppression, calculez et vérifiez le nombre de représentants des parents différents dans la structure de données.
Le nombre de résultats représente la connectivité du composant de mise à jour de l'arborescence.
Exemple
#include <iostream> #include <vector> class UnionFind { public: UnionFind(int n) { parent.resize(n); for (int i = 0; i < n; ++i) { parent[i] = i; } } int find(int u) { if (parent[u] != u) { parent[u] = find(parent[u]); } return parent[u]; } void unite(int u, int v) { int rootU = find(u); int rootV = find(v); if (rootU != rootV) { parent[rootU] = rootV; } } int countDistinctParentRepresentatives() { int n = parent.size(); std::vector<bool> distinct(n, false); for (int i = 0; i < n; ++i) { distinct[find(i)] = true; } int count = 0; for (bool isDistinct : distinct) { if (isDistinct) { count++; } } return count; } private: std::vector<int> parent; }; int main() { int n = 5; UnionFind uf(n); uf.unite(0, 1); uf.unite(0, 2); uf.unite(2, 3); uf.unite(2, 4); std::cout << uf.countDistinctParentRepresentatives() << std::endl; return 0; }
Sortie
1
Conclusion
En résumé, la méthode présentée peut compter efficacement le nombre de parties connectées dans l'arborescence après avoir supprimé un sommet spécifique. Les changements de connectivité dans les structures arborescentes peuvent être gérés efficacement à l'aide de méthodes de recherche en profondeur (DFS) et de méthodes de recherche par union. La méthode DFS démarre le parcours à partir du sommet sélectionné, marque chaque nœud visité et compte les composants connectés. Le décompte mis à jour est obtenu en comparant les décomptes de parcours avant et après après la suppression du sommet, et un nouveau parcours est effectué sans inclure le nœud supprimé.
Le nombre initial de composants connectés est déterminé à l'aide d'une opération d'union via la méthode Union-Find, qui initialise chaque sommet en tant que composant distinct. Appliquez la même opération d'union après avoir supprimé les sommets et comptez les différents représentants des parents pour obtenir un décompte mis à jour.
Les deux méthodes peuvent fournir des informations utiles sur la connectivité de l'arbre une fois les sommets supprimés et conviennent à une variété de scénarios.
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!

Outils d'IA chauds

Undresser.AI Undress
Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover
Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool
Images de déshabillage gratuites

Clothoff.io
Dissolvant de vêtements AI

AI Hentai Generator
Générez AI Hentai gratuitement.

Article chaud

Outils chauds

Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise
Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP

Dreamweaver CS6
Outils de développement Web visuel

SublimeText3 version Mac
Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Sujets chauds

Cet article détaille les types de retour de la fonction C, englobant de base (int, float, char, etc.), dérivé (tableaux, pointeurs, structures) et types de vide. Le compilateur détermine le type de retour via la déclaration de fonction et l'instruction de retour, appliquant

Gulc est une bibliothèque C haute performance priorisant les frais généraux minimaux, l'inclinaison agressive et l'optimisation du compilateur. Idéal pour les applications critiques de performance comme le trading à haute fréquence et les systèmes intégrés, sa conception met l'accent sur la simplicité, le module

Cet article explique la déclaration de la fonction C par rapport à la définition, l'argument passant (par valeur et par pointeur), les valeurs de retour et les pièges communs comme les fuites de mémoire et les décalages de type. Il souligne l'importance des déclarations de modularité et de provi

Cet article détaille les fonctions C pour la conversion de cas de chaîne. Il explique l'utilisation de Toupper () et Tolower () de Ctype.h, itérant à travers les cordes et manipulant des terminateurs nuls. Les pièges communs comme oublier Ctype.h et modifier les littéraux de chaîne sont

Cet article examine le stockage de valeur de retour de la fonction C. De petites valeurs de retour sont généralement stockées dans les registres pour la vitesse; Des valeurs plus importantes peuvent utiliser des pointeurs vers la mémoire (pile ou tas), impactant la durée de vie et nécessitant une gestion manuelle de la mémoire. ACC directement

Cet article analyse les utilisations à multiples facettes de l'adjectif "distinct" "explorant ses fonctions grammaticales, des phrases communes (par exemple," distinctes de "" "distinctement différentes") et une application nuancée en formelle vs informelle informelle

Cet article détaille l'utilisation efficace de l'algorithme STL en c. Il met l'accent sur le choix de la structure des données (vecteurs vs listes), l'analyse de la complexité des algorithmes (par exemple, STD :: Srieur vs std :: partial_sort), l'utilisation des itérateurs et l'exécution parallèle. Pièges communs comme

Cet article explique la bibliothèque de modèles standard C (STL), en se concentrant sur ses composants principaux: conteneurs, itérateurs, algorithmes et fonctors. Il détaille comment ces interagissent pour permettre la programmation générique, l'amélioration de l'efficacité du code et de la lisibilité
