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

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

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

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

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

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

memset(vis, false, sizeof(vis));
memset(pathVisit, false, sizeof(pathVisit));
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;
    pathVisit[parent] = true;
    for (int child : adj[parent])
    {
        if (pathVisit[child])
        {
            ans = true;
        }
        if (!vis[child])
        {
            dfs(child);
        }
    }
    // kaj sesh
    pathVisit[parent] = false;
}

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

---

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

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
bool vis[N];
bool pathVisit[N];
vector<int> adj[N];
bool ans;
void dfs(int parent)
{
    vis[parent] = true;
    pathVisit[parent] = true;
    for (int child : adj[parent])
    {
        if (pathVisit[child])
        {
            ans = true;
        }
        if (!vis[child])
        {
            dfs(child);
        }
    }
    // kaj sesh
    pathVisit[parent] = false;
}
int main()
{
    int n, e;
    cin >> n >> e;
    while (e--)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
    }
    memset(vis, false, sizeof(vis));
    memset(pathVisit, false, sizeof(pathVisit));
    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;
}