इस लेख में, हम ग्राफ में सिंक नोड्स की संख्या को हल करने पर महत्वपूर्ण जानकारी का वर्णन करेंगे। हमारे पास इस समस्या में N नोड्स (1 से N) और M एज के साथ एक डायरेक्टेड एसाइक्लिक ग्राफ है। लक्ष्य दिए गए ग्राफ में कितने सिंक नोड्स हैं, यह पता लगाना है। एक सिंक नोड वह नोड है जो कोई आउटगोइंग एज उत्पन्न नहीं करता है। तो यहाँ एक सरल उदाहरण है:
Input : n = 4, m = 2 Edges[] = {{2, 3}, {4, 3}} Output : 2समाधान खोजने का सरल दृष्टिकोण
इस दृष्टिकोण में, हम ग्राफ के एज के माध्यम से जाएंगे, सेट में उन विशिष्ट तत्वों को डालेंगे जिनसे एज जा रहे हैं, और फिर सेट के आकार को मौजूद कुल नोड्स की संख्या से घटाएंगे।
उदाहरण
#include <bits/stdc++.h> using namespace std; int main(){ int n = 4; // नोड्स की संख्या int m = 2; // एज की संख्या vector<pair<int, int>> edges = {{2, 3}, {4, 3}}; // पहले से दूसरे में जाने वाले एज set<int> s; for(int i = 0; i < m; i++){ s.insert(edges[i].first); // विशिष्ट नोड का मान रखेगा // जिससे एज बाहर जा रहे हैं } cout << n - s.size(); // उत्तर कुल नोड्स की संख्या - नॉन-सिंक नोड्स की संख्या return 0; }आउटपुट
2
उपरोक्त कोड की व्याख्या
इस कोड में, हम वेक्टर एज के माध्यम से पार करेंगे और जोड़ी के पहले तत्व को एक सेट में डालेंगे। यह केवल विशिष्ट तत्वों को रखता है, इसलिए अब हम सेट के विशिष्ट आकार को कुल नोड्स की संख्या से घटाएंगे। उपरोक्त दिखाए गए प्रोग्राम की समय जटिलता O(N) है जिसमें N ग्राफ में मौजूद एज की संख्या को दर्शाता है।
निष्कर्ष
इस लेख में, हम सेट की मदद से O(N) समय जटिलता में ग्राफ में मौजूद सिंक नोड्स की संख्या ज्ञात करने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण भी सीखा जिससे हमने इस समस्या को हल किया। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं। आशा है आपको यह लेख उपयोगी लगा होगा।