class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {

        int n = (int)prerequisites.size();

        vector<vector<int>>g(numCourses);
        vector<int>visit(numCourses,0);

        for ( auto it: prerequisites )
        {
            g[ it[1] ].push_back( it[ 0 ] );
        }

        vector<int>order;

        for(int i=0;i<numCourses;i++)
        {
            if(!visit[i])
            {
              auto it = dfs(i, g, visit, order);
                if(it) return {};


            }
        }

       reverse(order.begin(), order.end());
        if(order.size() != numCourses) return {};
       return order;

    }

    bool dfs( int node, vector<vector<int>>&g, vector<int>&visit, vector<int>&order )
    {

        visit[ node ] = 1;

        bool has_cycle = false;

        for( int child : g[node] )
        {
            if( visit[child] == 0)
            {
                has_cycle |= dfs(child, g, visit, order );
            }

            else if( visit[ child ] == 1 )
            {
                has_cycle = true;
            }
        }

        order.push_back(node);
        visit[ node ]=2;
        return has_cycle;
    }


};