सभी चक्रों को C++ में एक अप्रत्यक्ष ग्राफ में प्रिंट करें

इस समस्या में, हमें एक अप्रत्यक्ष ग्राफ दिया जाता है और हमें ग्राफ में बनने वाले सभी चक्रों को प्रिंट करना होता है।

अप्रत्यक्ष ग्राफ़ एक ग्राफ है जो एक साथ जुड़ा हुआ है। यूनिडायरेक्शनल ग्राफ के सभी किनारे द्विदिश हैं। इसे एक अप्रत्यक्ष नेटवर्क के रूप में भी जाना जाता है।

साइकिल ग्राफ़ में डेटा संरचना एक ऐसा ग्राफ़ होता है जिसमें सभी शीर्ष एक चक्र बनाते हैं।

आइए समस्या को बेहतर ढंग से समझने के लिए एक उदाहरण देखें -

ग्राफ़-

<मजबूत>

आउटपुट-

Cycle 1: 2 3 4 5
Cycle 2: 6 7 8

इसके लिए हम आलेख के कुछ गुणों का उपयोग करेंगे। आपको ग्राफ कलरिंग विधि का उपयोग करने और चक्रीय ग्राफ में आने वाले सभी शीर्षों को रंगने की आवश्यकता है। इसके अलावा, यदि एक शीर्ष आंशिक रूप से देखा जाता है, तो यह एक चक्रीय ग्राफ को जन्म देगा। इसलिए, हम इस शीर्ष और अगले सभी शीर्षों को तब तक रंगेंगे जब तक कि यह फिर से समान न हो जाए।

एल्गोरिदम

Step 1: call DFS traversal for the graph which can color the vertices.
Step 2: If a partially visited vertex is found, backtrack till the vertex is
reached again and mark all vertices in the path with a counter which is cycle number.
Step 3: After completion of traversal, iterate for cyclic edge and push them
into a separate adjacency list.
Step 4: Print the cycles number wise from the adjacency list.

उदाहरण

#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
vector<int> graph[N];
vector<int> cycles[N];
void DFSCycle(int u, int p, int color[], int mark[], int par[], int&amp; cyclenumber){
   if (color[u] == 2) {
      return;
   }
   if (color[u] == 1) {
      cyclenumber++;
      int cur = p;
      mark[cur] = cyclenumber;
      while (cur != u) {
         cur = par[cur];
         mark[cur] = cyclenumber;
      }
      return;
   }
   par[u] = p;
   color[u] = 1;
   for (int v : graph[u]) {
      if (v == par[u]) {
         continue;
      }
      DFSCycle(v, u, color, mark, par, cyclenumber);
   }
   color[u] = 2;
}
void insert(int u, int v){
   graph[u].push_back(v);
   graph[v].push_back(u);
}
void printCycles(int edges, int mark[], int&amp; cyclenumber){
   for (int i = 1; i <= edges; i++) {
      if (mark[i] != 0)
         cycles[mark[i]].push_back(i);
   }
   for (int i = 1; i <= cyclenumber; i++) {
      cout << "Cycle " << i << ": ";
      for (int x : cycles[i])
         cout << x << " ";
      cout << endl;
   }
}
int main(){
   insert(1, 2);
   insert(2, 3);
   insert(3, 4);
   insert(4, 5);
   insert(5, 2);
   insert(5, 6);
   insert(6, 7);
   insert(7, 8);
   insert(6, 8);
   int color[N];
   int par[N];
   int mark[N];
   int cyclenumber = 0;
   cout<<"Cycles in the Graph are :\n";
   int edges = 13;
   DFSCycle(1, 0, color, mark, par, cyclenumber);
   printCycles(edges, mark, cyclenumber);
}

आउटपुट

ग्राफ में चक्र हैं -

Cycle 1: 2 3 4 5
Cycle 2: 6 7 8