সি++-এ ডিপেন্ডেন্সি থেকে টাস্কের অর্ডারিং বের করুন (টপোলজিক্যাল সোর্ট)

সমস্যা বিবরণ

n সংখ্যক টাস্ক আছে (০ থেকে n-1 লেবেল্ড)। কিছু টাস্কের প্রিরিকুইজিট থাকতে পারে, যেমন টাস্ক ২ করার আগে টাস্ক ১ করতে হবে, এটি জোড়া [2, 1]-তে প্রকাশ করা হয়। টাস্ক সংখ্যা এবং প্রিরিকুইজিট জোড়াগুলো দিয়ে সব টাস্ক শেষ করার একটি অর্ডার বের করতে হবে। একাধিক সঠিক অর্ডার থাকলে যেকোনো একটি দিলে চলবে। অসম্ভব হলে খালি অ্যারে রিটার্ন করুন।

উদাহরণস্বরূপ, n=4, A=[[1,0],[2,0],[3,2],[3,1],[4,2]] হলে আউটপুট [0,2,1,4,3]।

সমাধানের ধাপসমূহ

1. গ্রাফ তৈরি করুন: graph[pre.second].insert(pre.first)।
2. ডিএফএস-ভিত্তিক টপোলজিক্যাল সোর্ট:
   • visited, onpath, toposort অ্যারে মেইনটেইন করুন।
   • dfs(graph, start, onpath, visited, toposort):
     • যদি visited[start] হয়, false রিটার্ন।
     • onpath[start] = visited[start] = true।
     • প্রতিটি নেইবর için: যদি onpath[neigh] অথবা ডিএফএস রিটার্ন true, তবে সাইকেল আছে -> true রিটার্ন।
     • toposort.push_back(start)।
     • onpath[start] = false রিটার্ন।
   • সব নোডের জন্য ডিএফএস চালান। সাইকেল পেলে খালি ভেক্টর রিটার্ন।
   • toposort রিভার্স করুন এবং রিটার্ন করুন।

সি++ কোড উদাহরণ

#include 
using namespace std;

vector> create_graph(int n, vector>& pre) {
    vector> graph(n);
    for (auto p : pre)
        graph[p.second].insert(p.first);
    return graph;
}

bool dfs(vector>& graph, int start,
         vector& onpath, vector& visited, vector& toposort) {
    if (visited[start]) return false;
    onpath[start] = visited[start] = true;
    for (int neigh : graph[start])
        if (onpath[neigh] || dfs(graph, neigh, onpath, visited, toposort))
            return true;
    toposort.push_back(start);
    return onpath[start] = false;
}

vector get_order(int n, vector>& pre) {
    vector> graph = create_graph(n, pre);
    vector toposort;
    vector onpath(n, false), visited(n, false);
    for (int i = 0; i < n; i++)
        if (!visited[i] && dfs(graph, i, onpath, visited, toposort))
            return {};
    reverse(toposort.begin(), toposort.end());
    return toposort;
}

int main() {
    int n = 4;
    vector> pre = {{1,0}, {2,0}, {3,2}, {3,1}, {4,0}};
    vector v = get_order(n, pre);
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << " ";
    return 0;
}

ইনপুট

4, {{1, 0}, {2, 0}, {3, 2}, {3, 1},{4,0}}

আউটপুট

0 1 4 2 3