Topological Sort 🚩🚩🚩

/*
    Whenever,in question there is something about dependency i.e if there is given something that this depend on other then first think of topological sort.


    Topological sort:-
            -> can be applied only on DAG->directed acyclic graph
            ->if there is directed edge from a to b then a will always come before the b in topo sort.


    How to find:-
        -> first algo
            ->while doing normal dfs after traversing the whole adjacency list push the curr node in stack and then after whole dfs just print the stack by poping each element.

        ->second algo
            ->KHANS's Algorithm
                Steps:-
                    1)give the indegree to each node while building the graph

                    2)now start from the node which has indegree 0 and push them into the queue

                    3)while,traversing the adjancecy list decrease the indegree of each child node

                    4)now,push only those element in the queue which has indegree 0

                    5)loop this till queue does not become empty

*/

typedef long long ll;
vector<ll> g[100001], visi(100001, 0), in(100001, 0);

//----------------------------------------------------------------------------------------

// dfs based approach
void topoSortUsingDfs(ll s, stack<ll> &st)
{
    if (visi[s])
        return;
    visi[s] = true;
    for (ll child : g[s])
    {
        if (visi[child] == false)
            topoSortUsingDfs(child, st);
    }

    st.push(s); // at last pushing the curr vertex in stack
}
    /*
       -->dfs based approach implementation in main function
       stack<ll> st;
       for (int i = 0; i < n; i++)
           if (visi[i] == false)
               topoSortUsingDfs(i, st);

       while (!st.empty())
       {
           cout << st.top() << " ";
           st.pop();
       }
    */

//----------------------------------------------------------------------------------------

// Khan's Algorithm
void khanAlgo(ll n)
{
    queue<ll> q;
    for (int i = 0; i < n; i++)
    {
        if (in[i] == 0)
        {
            q.push(i);//firstly pushing all the vertices with indegree 0 in queue.
            visi[i] = true;
        }
    }
    vector<int> topoSort;
    while (!q.empty())
    {
        ll curr = q.front();
        q.pop();
        topoSort.push_back(curr); // pushing the curr in to vector
        for (ll child : g[curr])
        {
            if (visi[child] == false)
                in[child]--;
            if (in[child] == 0)
            {
                q.push(child); // push only those element which has indegree 0
                visi[child] = true;
            }
        }
    }
}

    /*
    //increasing the indegree of each vertex
    while (m--)
    {
        ll s, d;
        cin >> s >> d;
        g[s].push_back(d);
        in[d]++; 
    }
     */