C++ প্রোগ্রাম: টাস্ক ডিপেন্ডেন্সি দিয়ে সব টাস্ক ফিনিশ করা সম্ভব কিনা চেক

টাস্কগুলো এবং তাদের প্রি-রেকুইজিট (প্রত্যাশা) দেওয়া আছে। সাইকেল থাকলে সব টাস্ক ফিনিশ করা যাবে না। গ্রাফ বানিয়ে DFS দিয়ে সাইকেল ডিটেক্ট করুন।

অ্যালগরিদম

1. ডিপেন্ডেন্সি লিস্ট থেকে ডাইরেক্টেড গ্রাফ বানান (u→v মানে v-এর আগে u করতে হয়)।
2. DFS ট্রাভার্সাল: onPath[] ট্র্যাক করুন বর্তমান পথে।
3. যদি onPath[neighbor] true পাওয়া যায় → সাইকেল → False।
4. সব নোড ভিজিট হলে True।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

vector<unordered_set<int>> makeGraph(int n, vector<pair<int,int>> &deps) {
    vector<unordered_set<int>> g(n);
    for (auto &p : deps) g[p.second].insert(p.first);
    return g;
}

bool hasCycle(vector<unordered_set<int>> &g, int u, vector<bool> &onPath, vector<bool> &vis) {
    if (vis[u]) return false;
    onPath[u] = vis[u] = true;
    for (int v : g[u])
        if (onPath[v] || hasCycle(g, v, onPath, vis)) return true;
    return onPath[u] = false;
}

bool canFinish(int n, vector<pair<int,int>> &deps) {
    auto g = makeGraph(n, deps);
    vector<bool> onPath(n), vis(n);
    for (int i=0; i

আউটপুট
True