हमें इनपुट के रूप में अविकलित और अवेटेड ग्राफ दिया गया है और कार्य दिए गए ग्राफ में बने चक्रों का गुणनफल खोजना और परिणाम प्रदर्शित करना है।
उदाहरण
इनपुट
दिए गए आंकड़े में, 8 नोड्स हैं और उनमें से 5 नोड्स 1, 6, 3, 5, 8 सहित चक्र बना रहे हैं और बाकी नोड्स चक्र में शामिल नहीं हैं। तो, चक्र की लंबाई 5 है क्योंकि इसमें 5 नोड्स शामिल हैं इसलिए गुणनफल 5 है
दिए गए आंकड़े में, 12 नोड्स हैं और उनमें से 11 (5 + 6) नोड्स 1, 6, 3, 5, 8 और 9, 4, 10, 11, 22, 12 सहित चक्र बना रहे हैं और बाकी नोड 2 चक्र में शामिल नहीं है। तो, चक्र की लंबाई 5 * 6 = 30 है
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है−
- चक्र बनाने के लिए नोड्स इनपुट करें
- DFS फ़ंक्शन बनाएं और इसे वर्टेक्स को रंगकर पार करने के लिए कॉल करें
- या तो नोड्स पूरी तरह से विज़िट किए गए हैं या आंशिक रूप से विज़िट किए गए हैं
- पूरी तरह से विज़िट किए गए नोड्स को फिर से विज़िट करने की आवश्यकता नहीं है और इसलिए उन्हें स्टोर करने की आवश्यकता नहीं है जबकि आंशिक रूप से विज़िट किए गए नोड्स को स्टोर करने की आवश्यकता है क्योंकि उन्हें फिर से विज़िट किया जाता है
- परिणाम प्रिंट करें
एल्गोरिदम
शुरुआत चरण 1-> DFS दृष्टिकोण का उपयोग करके ग्राफ को पार करने के लिए फ़ंक्शन घोषित करें void DFS(int i, int j, int color[], int highlight[], int parent[], int& number) IF color[i] = 2 वापस करें अंत IF color[i] = 1 number++ सेट करें int temp = j घोषित करें और सेट करें highlight[temp] = number सेट करें लूप जब तक temp != i temp = parent[temp] सेट करें highlight[temp] = number सेट करें अंत वापस करें अंत parent[i] = j सेट करें color[i] = 1 सेट करें int k के लिए : graph[i] IF k = parent[i] जारी रखें अंत DFS(k, i, color, highlight, parent, number) कॉल करें अंत color[i] = 2 सेट करें चरण 2-> चक्र में नोड्स के गुणनफल को खोजने के लिए फ़ंक्शन घोषित करें int product(int edge, int highlight[], int& number) unordered_map<int, int> mp कॉल करें लूप i = 1 से i <= edge और i++ तक IF (highlight[i] != 0) mp[highlight[i]]++ सेट करें अंत अंत int temp = 1 घोषित करें और सेट करें लूप i = 1 से i <= number और i++ तक temp = temp * mp[i] सेट करें अंत IF number = 0 temp = 0 सेट करें अंत temp वापस करें चरण 3-> main() में नोड सम्मिलित करने के लिए insert(1, 2) फ़ंक्शन कॉल करें int color[size], parent[size] घोषित करें int highlight[size] घोषित करें int number = 0 घोषित करें और सेट करें int edge = 10 घोषित करें और सेट करें DFS(1, 0, color, highlight, parent, number) कॉल करें product(edge, highlight, number) के रूप में प्रिंट फ़ंक्शन कॉल करें रुकें
उदाहरण
#include <bits/stdc++.h> using namespace std; const int size = 100000; vector<int> graph[size]; //DFS दृष्टिकोण का उपयोग करके ग्राफ को पार करने के लिए फ़ंक्शन void DFS(int i, int j, int color[], int highlight[], int parent[], int& number) { // पार किए गए नोड के लिए if (color[i] == 2) { return; } // पूरी तरह से विज़िट नहीं किया गया if (color[i] == 1) { number++; int temp = j; highlight[temp] = number; // वर्टेक्स को बैकट्रैक करने के लिए while (temp != i) { temp = parent[temp]; highlight[temp] = number; } return; } parent[i] = j; color[i] = 1; for (int k : graph[i]) { if (k == parent[i]) { continue; } DFS(k, i, color, highlight, parent, number); } color[i] = 2; } // ग्राफ में किनारे सम्मिलित करने के लिए फ़ंक्शन void insert(int u, int v) { graph[u].push_back(v); graph[v].push_back(u); } // चक्र में नोड्स का गुणनफल खोजें int product(int edge, int highlight[], int& number) { unordered_map<int, int> mp; for (int i = 1; i <= edge; i++) { if (highlight[i] != 0) mp[highlight[i]]++; } int temp = 1; for (int i = 1; i <= number; i++) { temp = temp * mp[i]; } if (number == 0) temp = 0; return temp; } int main() { // ग्राफ में नोड सम्मिलित करने के लिए insert(1, 2); insert(2, 3); insert(3, 4); insert(4, 6); insert(4, 7); insert(5, 6); insert(3, 5); insert(7, 8); insert(6, 10); insert(5, 9); insert(10, 11); int color[size], parent[size]; int highlight[size]; int number = 0; int edge = 10; DFS(1, 0, color, highlight, parent, number); // चक्रों को प्रिंट करने के लिए फ़ंक्शन cout<<"चक्र में सभी नोड्स का गुणनफल है : "<< product(edge, highlight, number); return 0; }आउटपुट
चक्र में सभी नोड्स का गुणनफल है :4
