> For the complete documentation index, see [llms.txt](https://phitron.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://phitron.gitbook.io/algorithm/cycle-detection/_-cycle-detection-directed-dfs.md).

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

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

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

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

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

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

```cpp
memset(vis, false, sizeof(vis));
memset(pathVisit, false, sizeof(pathVisit));
ans = false;
```

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

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

```cpp
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 করতে পারি।&#x20;

***

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

```cpp
#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;
}
```