এই সমস্যায়, আমাদেরকে একটি অনির্দেশিত গ্রাফ দেওয়া হয়েছে এবং গ্রাফে তৈরি হওয়া সমস্ত চক্র আমাদের প্রিন্ট করতে হবে৷
অনির্দেশিত গ্রাফ একটি গ্রাফ যা একসাথে সংযুক্ত। একমুখী গ্রাফের সমস্ত প্রান্ত দ্বিমুখী। এটি একটি অনির্দেশিত নেটওয়ার্ক হিসাবেও পরিচিত৷
৷চক্র একটি গ্রাফ ডেটা স্ট্রাকচারে একটি গ্রাফ যেখানে সমস্ত শীর্ষবিন্দু একটি চক্র গঠন করে।
সমস্যাটি আরও ভালোভাবে বোঝার জন্য একটি উদাহরণ দেখি -
গ্রাফ-
আউটপুট-
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& 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& 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
