এই সমস্যায়, একটি অনডিরেক্টেড গ্রাফ দেওয়া থাকে এবং আমাদের গ্রাফে তৈরি হওয়া সব সাইকেল প্রিন্ট করতে হবে।
অনডিরেক্টেড গ্রাফ হলো একটি গ্রাফ যা একসাথে সংযুক্ত থাকে। অনডিরেক্টেড গ্রাফের সব এজ বাইডিরেকশনাল। এটিকে অনডিরেক্টেড নেটওয়ার্কও বলা হয়।
সাইকেল গ্রাফ ডেটা স্ট্রাকচারে এমন একটি গ্রাফ যেখানে সব ভার্টেক্স একটি সাইকেল তৈরি করে।
উদাহরণ দিয়ে বুঝি:
গ্রাফ:
আউটপুট:
Cycle 1: 2 3 4 5 Cycle 2: 6 7 8
এই জন্য, আমরা গ্রাফের কয়েকটি প্রোপার্টি ব্যবহার করব। আপনাকে গ্রাফ কালারিং মেথড ব্যবহার করতে হবে এবং সাইকেল গ্রাফে থাকা ভার্টেক্সগুলো কালার করতে হবে। এছাড়া, যদি একটি ভার্টেক্স আংশিকভাবে ভিজিটেড থাকে, তবে সেটি একটি সাইকেল গ্রাফ তৈরি করে। তাই আমরা এই ভার্টেক্স এবং এরপরবর্তী সব ভার্টেক্স কালার করব যতক্ষণ না সেমি ভার্টেক্সটি আবার পাওয়া যায়।
অ্যালগরিদম
ধাপ ১: গ্রাফের জন্য DFS ট্রাভার্সাল কল করুন যা ভার্টেক্স কালার করতে পারে। ধাপ ২: যদি আংশিকভাবে ভিজিটেড ভার্টেক্স পাওয়া যায়, তখন সেই ভার্টেক্স পর্যন্ত ব্যাকট্র্যাক করুন এবং পথের সব ভার্টেক্সকে একটি কাউন্টার দিয়ে মার্ক করুন যা সাইকেল নম্বর। ধাপ ৩: ট্রাভার্সাল সম্পন্ন হলে, সাইকেলিক এজের জন্য ইটারেট করুন এবং সেগুলো আলাদা একটি অ্যাডজেসেন্সি লিস্টে পুশ করুন। ধাপ ৪: অ্যাডজেসেন্সি লিস্ট থেকে সাইকেল নম্বর অনুযায়ী প্রিন্ট করুন।
C++ উদাহরণ
#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
