この問題では、バイナリ ツリーを取得し、特定のノードから dfs を実行する必要があります。指定されたノードをルートとして想定し、そこから dfs を実行します。
上記のツリーでは、DFS ノード F
を実行する必要があると仮定しています。このチュートリアルでは、時間を大幅に削減するために、いくつかの型破りな方法を適用します。したがって、より高い制約の下でこのコードを実行することもできます。
メソッド - このアプローチでは、単純なアプローチは採用しません。つまり、より高い制約では機能しないため、各ノードに dfs を適用するだけです。そのため、いくつかの型破りなアプローチを使用しようとします。 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'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'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'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'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; }
The DFS of subtree 2: 2 4 6 7 5 The DFS of subtree 4: 4 6 7
このメソッドでは、dfs の次数を事前計算してベクトルに格納します。dfs を事前計算するときに、次数もカウントします。各ノードから開始して各サブツリーの下に存在するノードを調べ、そのノードの開始インデックスからそのサブツリーに存在するすべてのノードの数まで単純にたどります。
このチュートリアルでは、ツリー内のサブツリーの DFS というクエリを解決する問題を解決しました。また、この問題に対する C プログラムと、この問題を解決するための完全な方法 (通常) も学習しました。
同じプログラムを他の言語 (C、Java、Python など) で書くことができます。この記事がお役に立てば幸いです。
以上がC++ を使用したツリー内のサブツリーの深さ優先検索の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。