इस समस्या में हमें एक बाइनरी ट्री दिया गया है और हमें एक विशेष नोड से DFS करना है जिसमें हम दिए गए नोड को रूट मानते हैं और उससे DFS करते हैं।
उपरोक्त ट्री में मान लें हमें नोड F से DFS करना है
इस ट्यूटोरियल में हम कुछ अपरंपरागत तरीके लागू करने जा रहे हैं ताकि हमारी समय जटिलता काफी कम हो जाए और इस प्रकार हम इस कोड को उच्च प्रतिबंधों के लिए भी चला सकें।
दृष्टिकोण - इस दृष्टिकोण में हम केवल सरल तरीके से नहीं जाने वाले हैं यानी जहां हम केवल हर नोड के लिए DFS लागू करते हैं क्योंकि यह उच्च प्रतिबंधों के लिए काम नहीं करेगा इसलिए हम TLE से बचने के लिए कुछ अपरंपरागत तरीकों का उपयोग करने की कोशिश करते हैं।
#include <bits/stdc++.h> using namespace std; #define N 100000 // ट्री नोड्स कनेक्शन स्टोर करने के लिए एडजेसेंसी लिस्ट vector<int> v[N]; unordered_map<int, int> mape; // नोड को उसके इंडेक्स के साथ जोड़ने के लिए उपयोग किया जाएगा vector<int> a; void dfs(int nodesunder[], int child, int parent){ // DFS के लिए फंक्शन और प्रीकैलकुलेशन हमारे nodesunder a.push_back(child); // हमारे ट्री का DFS स्टोर करना // चाइल्ड सबट्री के nodesunder nodesunder[child] = 1; for (auto it : v[child]) { // सामान्य DFS करना if (it != parent) { // चूंकि चाइल्ड अपने पैरेंट तक चढ़ सकता है // इसलिए हम उससे बचने की कोशिश कर रहे हैं क्योंकि यह एक चक्र बन जाएगा dfs(nodesunder, it, child); // रिकर्सिव कॉल nodesunder[child] += nodesunder[it]; // nodesunder को बढ़ाना // इसके बच्चों के नीचे मौजूद नोड्स की संख्या से } } } // सबट्री के DFS को प्रिंट करने का फंक्शन void printDFS(int node, int nodesunder[]){ int ind = mape[node]; // DFS सरणी में हमारे नोड का इंडेक्स cout << "The DFS of subtree " << node << ": "; // सबट्री का DFS प्रिंट करना for (int i = ind; i < ind + nodesunder[node]; i++){ // DFS सरणी के माध्यम से जाना और फिर // हमारे दिए गए नोड के तहत सभी नोड्स प्रिंट करना cout << a[i] << " "; } cout << endl; } void addEdgetoGraph(int x, int y){ // एडजेसेंसी लिस्ट बनाए रखने के लिए v[x].push_back(y); v[y].push_back(x); } void mark(){ // DFS सरणी में प्रत्येक नोड को उसके इंडेक्स के साथ चिह्नित करना int size = a.size(); // इंडेक्स चिह्नित करना for (int i = 0; i < size; i++) { mape[a[i]] = i; } } int main(){ int n = 7; // ट्री के एज जोड़ना addEdgetoGraph(1, 2); addEdgetoGraph(1, 3); addEdgetoGraph(2, 4); addEdgetoGraph(2, 5); addEdgetoGraph(4, 6); addEdgetoGraph(4, 7); // हर नोड के सबट्री में मौजूद नोड्स स्टोर करने के लिए सरणी int nodesunder[n + 1]; dfs(nodesunder, 1, 0); // हमारा nodesunder सरणी जनरेट करना mark(); // मैप में इंडेक्स चिह्नित करना // क्वेरी 1 printDFS(2, nodesunder); // क्वेरी 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 और अन्य भाषाओं में भी लिख सकते हैं। आशा है आपको यह लेख उपयोगी लगा होगा।
