C++ এ একটি অনির্দেশিত গ্রাফে সমস্ত চক্রের দৈর্ঘ্যের গুণফল

আমাদেরকে ইনপুট হিসাবে অনির্দেশিত এবং ওজনহীন গ্রাফ দেওয়া হয়েছে এবং কাজ হল প্রদত্ত চক্রের গুণফল খুঁজে বের করা এবং ফলাফল প্রদর্শন করা।

উদাহরণ

ইনপুট

প্রদত্ত চিত্রে, 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 ফাংশন তৈরি করুন এবং এটিকে রঙ করার মাধ্যমে শীর্ষবিন্দু অতিক্রম করতে কল করুন
• হয় নোডটিকে সম্পূর্ণরূপে পরিদর্শন করা বা আংশিকভাবে পরিদর্শন করা হিসাবে চিহ্নিত করা হয়েছে
• সম্পূর্ণভাবে পরিদর্শন করা নোডগুলিকে আবার দেখার প্রয়োজন নেই এবং তাই এটি সংরক্ষণ করার প্রয়োজন নেই যেখানে আংশিকভাবে পরিদর্শন করা নোডগুলিকে সংরক্ষণ করতে হবে কারণ সেগুলি আবার পরিদর্শন করা হয়েছে
• ফলাফল প্রিন্ট করুন

অ্যালগরিদম

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