ในปัญหานี้ เราได้รับไบนารีทรีและเราจำเป็นต้องดำเนินการ 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++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ ( Normal) ซึ่งเราแก้ปัญหานี้ได้
เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ หวังว่าบทความนี้จะเป็นประโยชน์
