Table des matières
Méthode à utiliser
Méthode de recherche en profondeur (DFS)
Algorithme
Exemple
Sortie
Et vérifiez la méthode
Conclusion
Maison développement back-end C++ Interroger le nombre de composants connectés après avoir supprimé un sommet de l'arborescence

Interroger le nombre de composants connectés après avoir supprimé un sommet de l'arborescence

Aug 26, 2023 pm 04:29 PM
Supprimer des sommets Interroger les composants connectés Quantité de portions

Interroger le nombre de composants connectés après avoir supprimé un sommet de larborescence

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;
}
Copier après la connexion

Sortie

5
Copier après la connexion

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;
}
Copier après la connexion

Sortie

1
Copier après la connexion

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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Meilleurs paramètres graphiques
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Comment réparer l'audio si vous n'entendez personne
1 Il y a quelques mois By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Commandes de chat et comment les utiliser
1 Il y a quelques mois By 尊渡假赌尊渡假赌尊渡假赌

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

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

C Structure des données du langage: représentation des données et fonctionnement des arbres et des graphiques C Structure des données du langage: représentation des données et fonctionnement des arbres et des graphiques Apr 04, 2025 am 11:18 AM

C Structure des données du langage: La représentation des données de l'arborescence et du graphique est une structure de données hiérarchique composée de nœuds. Chaque nœud contient un élément de données et un pointeur vers ses nœuds enfants. L'arbre binaire est un type spécial d'arbre. Chaque nœud a au plus deux nœuds enfants. Les données représentent StrustReenode {intdata; structTreenode * gauche; structureReode * droite;}; L'opération crée une arborescence d'arborescence arborescence (prédécision, ordre dans l'ordre et ordre ultérieur) Le nœud d'insertion de l'arborescence des arbres de recherche de nœud Graph est une collection de structures de données, où les éléments sont des sommets, et ils peuvent être connectés ensemble via des bords avec des données droites ou peu nombreuses représentant des voisins.

La vérité derrière le problème de fonctionnement du fichier de langue C La vérité derrière le problème de fonctionnement du fichier de langue C Apr 04, 2025 am 11:24 AM

La vérité sur les problèmes de fonctionnement des fichiers: l'ouverture des fichiers a échoué: les autorisations insuffisantes, les mauvais chemins de mauvais et les fichiers occupés. L'écriture de données a échoué: le tampon est plein, le fichier n'est pas écrivatif et l'espace disque est insuffisant. Autres FAQ: traversée de fichiers lents, encodage de fichiers texte incorrect et erreurs de lecture de fichiers binaires.

Comment utiliser efficacement les références RValue en C? Comment utiliser efficacement les références RValue en C? Mar 18, 2025 pm 03:29 PM

L'article discute de l'utilisation efficace des références de référence en C pour la sémantique de déplacement, le transfert parfait et la gestion des ressources, mettant en évidence les meilleures pratiques et les améliorations des performances. (159 caractères)

Comment utiliser les plages dans C 20 pour une manipulation de données plus expressive? Comment utiliser les plages dans C 20 pour une manipulation de données plus expressive? Mar 17, 2025 pm 12:58 PM

Les plages de c 20 améliorent la manipulation des données avec l'expressivité, la composibilité et l'efficacité. Ils simplifient les transformations complexes et s'intègrent dans les bases de code existantes pour de meilleures performances et maintenabilité.

Quelles sont les exigences de base pour les fonctions de langue C Quelles sont les exigences de base pour les fonctions de langue C Apr 03, 2025 pm 10:06 PM

Les fonctions de langue C sont la base de la modularisation du code et de la construction de programmes. Ils se composent de déclarations (en-têtes de fonction) et de définitions (corps de fonction). Le langage C utilise des valeurs pour transmettre les paramètres par défaut, mais les variables externes peuvent également être modifiées à l'aide d'adresse Pass. Les fonctions peuvent avoir ou ne pas avoir de valeur de retour et le type de valeur de retour doit être cohérent avec la déclaration. La dénomination de la fonction doit être claire et facile à comprendre, en utilisant un chameau ou une nomenclature de soulignement. Suivez le principe de responsabilité unique et gardez la simplicité de la fonction pour améliorer la maintenabilité et la lisibilité.

Comment calculer C-SUBScript 3 Indice 5 C-SUBScript 3 Indice Indice 5 Tutoriel d'algorithme Comment calculer C-SUBScript 3 Indice 5 C-SUBScript 3 Indice Indice 5 Tutoriel d'algorithme Apr 03, 2025 pm 10:33 PM

Le calcul de C35 est essentiellement des mathématiques combinatoires, représentant le nombre de combinaisons sélectionnées parmi 3 des 5 éléments. La formule de calcul est C53 = 5! / (3! * 2!), Qui peut être directement calculé par des boucles pour améliorer l'efficacité et éviter le débordement. De plus, la compréhension de la nature des combinaisons et la maîtrise des méthodes de calcul efficaces est cruciale pour résoudre de nombreux problèmes dans les domaines des statistiques de probabilité, de la cryptographie, de la conception d'algorithmes, etc.

Comment utiliser Move Semantics en C pour améliorer les performances? Comment utiliser Move Semantics en C pour améliorer les performances? Mar 18, 2025 pm 03:27 PM

L'article discute de l'utilisation de Move Semantics en C pour améliorer les performances en évitant la copie inutile. Il couvre la mise en œuvre de constructeurs de déplace

Comment le répartition dynamique fonctionne-t-il en C et comment affecte-t-il les performances? Comment le répartition dynamique fonctionne-t-il en C et comment affecte-t-il les performances? Mar 17, 2025 pm 01:08 PM

L'article traite de Dynamic Dispatch in C, ses coûts de performance et les stratégies d'optimisation. Il met en évidence les scénarios où la répartition dynamique a un impact

See all articles