Recherche en profondeur des sous-arbres dans un arbre en utilisant C++

Dans ce problème, nous obtenons un arbre binaire et nous devons exécuter dfs à partir d'un nœud spécifique, où nous prenons le nœud donné comme racine et exécutons dfs à partir de celui-ci.

Dans l'arborescence ci-dessus, supposons que nous devions exécuter le nœud DFS F

Dans ce tutoriel, nous appliquerons des méthodes peu orthodoxes afin de réduire considérablement notre complexité temporelle afin que nous puissions également exécuter à un niveau plus élevé. Exécutez ce code sous contraintes.

Méthode - Dans cette approche, nous n'optons pas pour l'approche naïve, c'est-à-dire que nous appliquons simplement dfs à chaque nœud car cela ne fonctionne pas pour des contraintes plus élevées, nous essayons donc d'utiliser quelque chose de peu orthodoxe pour éviter d'obtenir un TLE.

#include <bits/stdc++.h>
using namespace std;
#define N 100000
// Adjacency list to store the
// tree nodes connections
vector<int> v[N];
unordered_map<int, int> mape; // will be used for associating the node with it&#39;s index
vector<int> a;
void dfs(int nodesunder[], int child, int parent){ // function for dfs and     precalculation our nodesunder
    a.push_back(child); // storing the dfs of our tree
    // nodesunder of child subtree
    nodesunder[child] = 1;
    for (auto it : v[child]) { // performing normal dfs

        if (it != parent) { // as we the child can climb up to
        //it&#39;s parent so we are trying to avoid that as it will become a cycle
            dfs(nodesunder, it, child); // recursive call
            nodesunder[child] += nodesunder[it]; // storing incrementing the nodesunder
        //by the number of nodes under it&#39;s children
        }
    }
}
// Function to print the DFS of subtree of node
void printDFS(int node, int nodesunder[]){
    int ind = mape[node]; // index of our node in the dfs array
    cout << "The DFS of subtree " << node << ": ";
    // print the DFS of subtree
    for (int i = ind; i < ind + nodesunder[node]; i++){ // going through dfs array and then
    //printing all the nodes under our given node
        cout << a[i] << " ";
    }
    cout << endl;
}
void addEdgetoGraph(int x, int y){ // for maintaining adjacency list
    v[x].push_back(y);
    v[y].push_back(x);
}
void mark(){ // marking each node with it&#39;s index in dfs array
    int size = a.size();
    // marks the index
    for (int i = 0; i < size; i++) {
       mape[a[i]] = i;
    }
}
int main(){
    int n = 7;
    // add edges of a tree
    addEdgetoGraph(1, 2);
    addEdgetoGraph(1, 3);
    addEdgetoGraph(2, 4);
    addEdgetoGraph(2, 5);
    addEdgetoGraph(4, 6);
    addEdgetoGraph(4, 7);
    // array to store the nodes present under of subtree
    // of every node in a tree
    int nodesunder[n + 1];
    dfs(nodesunder, 1, 0); // generating our nodesunder array
    mark(); // marking the indices in map
    // Query 1
    printDFS(2, nodesunder);
    // Query 2
    printDFS(4, nodesunder);
    return 0;
}

Sortie

The DFS of subtree 2: 2 4 6 7 5
The DFS of subtree 4: 4 6 7

Comprendre le code

Dans cette méthode, nous précalculons l'ordre des dfs et le stockons dans un vecteur, lorsque nous précalculons dfs, nous calculons également chaque sous-arbre à partir de chaque nœud qui existe sous then, puis nous avons simplement passe de l'index de départ du nœud au nombre de tous les nœuds qui existent dans son sous-arbre.

Conclusion

Dans ce tutoriel, nous avons résolu un problème pour résoudre la requête suivante : DFS de sous-arbres dans un arbre. Nous avons également appris un programme C++ pour ce problème et une méthode complète pour résoudre ce problème (Normal).

Nous pouvons écrire le même programme dans d'autres langages (comme C, java, python, etc.). J'espère que cet article vous sera utile.

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!