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