हमें इनपुट के रूप में अप्रत्यक्ष के साथ-साथ बिना भार वाले ग्राफ दिए गए हैं और कार्य दिए गए चक्रों के उत्पाद को खोजना और परिणाम प्रदर्शित करना है।
उदाहरण
इनपुट
दी गई आकृति में, 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
. हैनीचे दिए गए कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है -
- चक्र बनाने के लिए नोड्स इनपुट करें
- डीएफएस फ़ंक्शन बनाएं और इसे रंग देकर शीर्ष को पार करने के लिए कॉल करें
- या तो नोड पूरी तरह से देखे गए या आंशिक रूप से देखे गए चिह्नित हैं
- पूरी तरह से देखे गए नोड को फिर से देखने की आवश्यकता नहीं है और इसलिए इसे संग्रहीत करने की आवश्यकता नहीं है जबकि आंशिक रूप से देखे गए नोड्स को संग्रहीत करने की आवश्यकता है क्योंकि वे फिर से देखे जाते हैं
- परिणाम प्रिंट करें
एल्गोरिदम
Start Step 1-> declare function to traverse the graph using DFS approach void DFS(int i, int j, int color[], int highlight[], int parent[], int& number) IF color[i] = 2 Return End IF color[i] = 1 Set number++ Declare and set int temp = j Set highlight[temp] = number Loop While temp != i Set temp = parent[temp] Set highlight[temp] = number End Return End Set parent[i] = j Set color[i] = 1 For int k : graph[i] IF k = parent[i] Continue End Call DFS(k, i, color, highlight, parent, number) End Set color[i] = 2 Step 2-> declare function to find product of nodes in cycle int product(int edge, int highlight[], int& number) call unordered_map<int, int> mp Loop For i = 1 and i <= edge and i++ IF (highlight[i] != 0) Set mp[highlight[i]]++ End End Declare and set int temp = 1 Loop For i = 1 and i <= number and i++ Set temp = temp * mp[i] End IF number = 0 Set temp = 0 End return temp Step 3-> In main() Call function as insert(1, 2) to insert a node Declare int color[size], parent[size] Declare int highlight[size] Declare and set int number = 0 Declare and set int edge = 10 Call DFS(1, 0, color, highlight, parent, number) Call print function as product(edge, highlight, number) Stop
उदाहरण
#include <bits/stdc++.h>
using namespace std;
const int size = 100000;
vector<int> graph[size];
//function to traverse the graph using DFS approach
void DFS(int i, int j, int color[], int highlight[], int parent[], int& number) {
// for travered node
if (color[i] == 2) {
return;
}
//not completely visited
if (color[i] == 1) {
number++;
int temp = j;
highlight[temp] = number;
//for backtracking the vertex
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;
}
// function for inserting edges to graph
void insert(int u, int v) {
graph[u].push_back(v);
graph[v].push_back(u);
}
// Find product of nodes in cycle
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() {
//for inserting a node in the graph
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);
// function to print the cycles
cout<<"product of all the nodes in the cycle is :"<< product(edge, highlight, number);
return 0;
} आउटपुट
Product of all the nodes in the cycle is :4