इस लेख में, हम एक ग्राफ में सिंक नोड्स की संख्या को हल करने के बारे में महत्वपूर्ण जानकारी का वर्णन करेंगे। हमारे पास इस समस्या में एन नोड्स (1 से एन) और एम किनारों के साथ एक निर्देशित चक्रीय ग्राफ है। लक्ष्य यह पता लगाना है कि दिए गए ग्राफ़ में कितने सिंक नोड हैं। एक सिंक नोड एक नोड है जो किसी भी आउटगोइंग किनारों का उत्पादन नहीं करता है। तो यहाँ एक सरल उदाहरण है -
Input : n = 4, m = 2
Edges[] = {{2, 3}, {4, 3}}
Output : 2 समाधान खोजने का आसान तरीका
इस दृष्टिकोण में, हम ग्राफ़ के किनारों के माध्यम से जाएंगे, उस सेट में अलग-अलग तत्वों को धक्का देंगे जिससे किनारे जा रहे हैं, और फिर सेट के आकार को कुल नोड्स के साथ घटाएं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int main(){
int n = 4; // number of nodes.
int m = 2; // number of edges.
vector<pair<int, int>> edges = {{2, 3}, {4, 3}}; // the edges going from first to second.
set<int> s;
for(int i = 0; i < m; i++){
s.insert(edges[i].first); // will keep value of
// distinct node from which edges are going out.
}
cout << n - s.size(); // answer is the total number of nodes - number of non sink nodes.
return 0;
} आउटपुट
2
उपरोक्त कोड की व्याख्या
इस कोड में, हम वेक्टर किनारों से गुजरेंगे और जोड़ी के पहले तत्व को एक सेट में डालेंगे। यह केवल विशिष्ट तत्वों को रखता है, इसलिए अब हम सेट के विशिष्ट आकार को नोड्स की कुल संख्या से घटा देंगे। ऊपर दिखाए गए कार्यक्रम में O(N) . की समय जटिलता है जिसमें N एक ग्राफ में मौजूद किनारों की संख्या को दर्शाता है।
निष्कर्ष
इस लेख में, हमने एक सेट की मदद से ग्राफ ओ (एन) समय जटिलता में मौजूद सिंक नोड्स की संख्या को खोजने की समस्या को हल किया। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा तरीका भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह लेख मददगार लगा होगा।