মডিউল ৫_৩ঃ Cycle Detection Undirected গ্রাফ DFS ইমপ্লিমেন্টশন

Cycle Detection Undirected গ্রাফ DFS ইমপ্লিমেন্টশন

আমরা এখন DFS দিয়ে cycle detection স্টেপ বাই স্টেপ কোড এ দেখার চেষ্টা করব।

এখানে প্রথমে আমরা মেইন ফাংশনটি বোঝার চেষ্টা করব। প্রথমে আমরা নোড সংখ্যা ও এডজ সংখ্যা ইনপুট নিয়েছি। এরপর একটি লুপের মাধ্যমে কোন নোড দুইটির মধ্যে এডজ থাকবে সেটা অ্যাডজেসেন্সি লিস্ট এর মধ্যে নিয়ে নিচ্ছি।

int n, e;
cin >> n >> e;
while (e--)
{
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
}

এবার ভিজিটেড এ্যারেটি ইনিশিয়ালাইজ করে নিচ্ছি false হিসেবে। parentArray এ্যারেটি ইনিশিয়ালাইজ করে নিচ্ছি -1 হিসেবে এবং ans কে false করে নিচ্ছি।

memset(vis, false, sizeof(vis));
memset(parentArray, -1, sizeof(parentArray));
ans = false;

এরপর number of nodes বার লুপ চালাচ্ছি এবং কোন নোড আনভিজিটেড হলে সেই নোডটি দিয়ে dfs function কে কল করতেছি।

for (int i = 0; i < n; i++)
{
    if (!vis[i])
    {
        dfs(i);
    }
}

void dfs(int parent)
{
    vis[parent] = true;
    // cout << parent << endl;
    for (int child : adj[parent])
    {
        if (vis[child] == true && child != parentArray[parent])
        {
            ans = true;
            // cout << parent << " " << child << " " << parentArray[parent] << endl;
        }
        if (vis[child] == false)
        {
            parentArray[child] = parent;
            dfs(child);
        }
    }
}

এইভাবে আমরা DFS দিয়ে undirected গ্রাফে cycle detect করতে পারি।

---

সম্পূর্ণ কোড Cycle Detection Undirected গ্রাফ DFS ইমপ্লিমেন্টশন

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
bool vis[N];
vector<int> adj[N];
int parentArray[N];
bool ans;
void dfs(int parent)
{
    vis[parent] = true;
    // cout << parent << endl;
    for (int child : adj[parent])
    {
        if (vis[child] == true && child != parentArray[parent])
        {
            ans = true;
            // cout << parent << " " << child << " " << parentArray[parent] << endl;
        }
        if (vis[child] == false)
        {
            parentArray[child] = parent;
            dfs(child);
        }
    }
}
int main()
{
    int n, e;
    cin >> n >> e;
    while (e--)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    memset(vis, false, sizeof(vis));
    memset(parentArray, -1, sizeof(parentArray));
    ans = false;
    for (int i = 0; i < n; i++)
    {
        if (!vis[i])
        {
            dfs(i);
        }
    }
    if (ans)
        cout << "Cycle detected";
    else
        cout << "Cycle not detected";
    return 0;
}