Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ का उपयोग करके ग्राफ में सिंक नोड्स की संख्या ज्ञात करें


इस लेख में, हम ग्राफ में सिंक नोड्स की संख्या को हल करने पर महत्वपूर्ण जानकारी का वर्णन करेंगे। हमारे पास इस समस्या में 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 और अन्य भाषाओं में लिख सकते हैं। आशा है आपको यह लेख उपयोगी लगा होगा।


  1. C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना

    इस लेख में, आप एक दी गई स्ट्रिंग में बनने वाले सबस्ट्रिंग्स (गैर-खाली) की संख्या निकालने के दृष्टिकोण के बारे में जानेंगे।इनपुट: string = moon आउटपुट: 10 व्याख्या: सबस्ट्रिंग्स हैं m, o, o, n, mo, oo, on, moo, oon और moon। इनपुट: string = yellow आउटपुट: 21समाधान खोजने का दृष्टिकोणमान लें स्ट्रिंग की

  1. C++ का उपयोग करके स्टॉपिंग स्टेशनों की संख्या ज्ञात करें C++ का उपयोग करके स्टॉपिंग स्टेशनों की संख्या ज्ञात करें

    बिंदु X और Y के बीच n संख्या में इंटरमीडिएट ट्रेन स्टेशन हैं। उन विभिन्न तरीकों की गणना करें जिनसे ट्रेनों को s स्टेशनों पर रुकने के लिए व्यवस्थित किया जा सकता है जैसे कि कोई दो स्टेशन एक-दूसरे के बगल में न हों। तो इस लेख में, हम स्टॉपिंग स्टेशनों की संख्या ज्ञात करने के लिए हर संभव दृष्टिकोण की व्य

  1. C++ का उपयोग करके एक सेट पर रिफ्लेक्सिव रिलेशंस की संख्या ज्ञात करें C++ का उपयोग करके एक सेट पर रिफ्लेक्सिव रिलेशंस की संख्या ज्ञात करें

    इस लेख में, हम एक सेट पर रिफ्लेक्सिव रिलेशंस की संख्या ज्ञात करने के दृष्टिकोणों की व्याख्या करेंगे। इस समस्या में, हमें संख्या n दी गई है, और n प्राकृतिक संख्याओं के एक सेट पर, हमें रिफ्लेक्सिव रिलेशंस की संख्या निर्धारित करनी है।रिफ्लेक्सिव रिलेशन - एक सेट A में एक रिलेशन को रिफ्लेक्सिव कहा जाता ह