অনিদেশিত গ্রাফে সাইকলের দৈর্ঘ্যের গুণফল C++-তে

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

উদাহরণ

ইনপুট

দেওয়া চিত্রে ৮টি নোড আছে য 그중 ৫টি নোড (১, ৬, ৩, ৫, ৮) সাইকেল গঠন করছে এবং বাকি নোডগুলো সাইকেলে নেই। তাই সাইকেলের দৈর্ঘ্য ৫ এবং গুণফল ৫।

দেওয়া চিত্রে ১২টি নোড আছে য 그중 ১১টি (৫ + ৬) নোড সাইকেল গঠন করছে: ১, ৬, ৩, ৫, ৮ এবং ৯, ৪, ১০, ১১, ২২, ১২। নোড ২ সাইকেলে নেই। তাই সাইকেলের দৈর্ঘ্য ৫ * ৬ = ৩০।

প্রোগ্রামে ব্যবহৃত পদ্ধতি -

• সাইকেল গঠনের জন্য নোডগুলো ইনপুট নেওয়া।
• DFS ফাংশন তৈরি করে কল করা এবং ভের্টেক্স ট্র্যাভার্স করতে রঙ করা।
• নোডগুলো либо সম্পূর্ণ ভিজিটেড হতে পারে বা আংশিকভাবে ভিজিটেড।
• স্পষ্ট ভিজিটেড নোড আবার ভিজিট করতে হয় না, তাই সংরক্ষণ করার দরকার নেই, কিন্তু আংশিক ভিজিটেড নোডগুলো আবার ভিজিট হতে পারে তাই সেগুলো সংরক্ষণ করা।
• ফলাফল প্রিন্ট করা।

অ্যালগরিদম

শুরু
ধাপ ১ -> DFS পদ্ধতিতে গ্রাফ ট্র্যাভার্সের ফাংশন ঘোষণা
    void DFS(int i, int j, int color[], int highlight[], int parent[], int& number)
    যদি color[i] == 2
        রিটার্ন
    শেষ
    যদি color[i] == 1
        number++
        int temp = j ঘোষণা এবং সেট
        highlight[temp] = number সেট
        লুপ যতক্ষণ temp != i
            temp = parent[temp] সেট
            highlight[temp] = number সেট
        শেষ
        রিটার্ন
    শেষ
    parent[i] = j সেট
    color[i] = 1 সেট
    int k : graph[i] এর জন্য
        যদি k == parent[i]
            কন্টিনিউ
        শেষ
        DFS(k, i, color, highlight, parent, number) কল
    শেষ
    color[i] = 2 সেট
ধাপ ২ -> সাইকেলের নোডের গুণফল বের করার ফাংশন ঘোষণা
    int product(int edge, int highlight[], int& number)
    unordered_map mp কল
    লুপ i = 1 থেকে i <= edge এবং i++
        যদি (highlight[i] != 0)
            mp[highlight[i]]++ সেট
        শেষ
    শেষ
    int temp = 1 ঘোষণা এবং সেট
    লুপ i = 1 থেকে i <= number এবং i++
        temp = temp * mp[i] সেট
    শেষ
    যদি number == 0
        temp = 0 সেট
    শেষ
    return temp
ধাপ ৩ -> main()-এ
    insert(1, 2) কল করে নোড ইনসার্ট
    int color[size], parent[size] ঘোষণা
    int highlight[size] ঘোষণা
    int number = 0 ঘোষণা এবং সেট
    int edge = 10 ঘোষণা এবং সেট
    DFS(1, 0, color, highlight, parent, number) কল
    প্রিন্ট ফাংশন হিসেবে product(edge, highlight, number) কল
শেষ

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
const int size = 100000;
vector graph[size];
// DFS পদ্ধতিতে গ্রাফ ট্র্যাভার্স
void DFS(int i, int j, int color[], int highlight[], int parent[], int& number) {
    // ট্র্যাভার্সড নোড
    if (color[i] == 2) {
        return;
    }
    // পুরোপুরি ভিজিটেড নয়
    if (color[i] == 1) {
        number++;
        int temp = j;
        highlight[temp] = number;
        // ভের্টেক্স ব্যাকট্র্যাকিং
        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;
}
// গ্রাফে এজ ইনসার্ট করার ফাংশন
void insert(int u, int v) {
    graph[u].push_back(v);
    graph[v].push_back(u);
}
// সাইকেলের নোডের গুণফল বের করা
int product(int edge, int highlight[], int& number) {
    unordered_map 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() {
    // গ্রাফে নোড ইনসার্ট
    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);
    // সাইকেল প্রিন্ট করার ফাংশন
    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