이 문제에서 우리는 이진 트리가 주어지고 주어진 노드를 루트로 가정하고 그 노드에서 dfs를 수행하는 특정 노드에서 dfs를 수행해야 합니다.
위의 트리에서 노드 F에서 DFS를 수행해야 한다고 가정합니다.
이 튜토리얼에서 우리는 시간 복잡도를 상당히 줄여 더 높은 제약 조건에 대해서도 이 코드를 실행할 수 있도록 몇 가지 비정통적인 방법을 적용할 것입니다.
접근 − 이 접근 방식에서 우리는 단순히 순진한 방법을 사용하지 않을 것입니다. 즉, 더 높은 제약 조건에서는 작동하지 않으므로 모든 노드에 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 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.