class Solution {


public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {

        int n = (int)prerequisites.size();
        vector<int>state(numCourses, 0);
        vector<vector<int>>g(numCourses);

        for(int i=0;i<n;i++)
        {
            g[prerequisites[i][1]].push_back(prerequisites[i][0]);
        }


        for(int i=0;i<numCourses;i++)
        {
            if(state[i] == 0)
            {
                if( dfs( i, g, state )) return false;
            }
        }

        return true;

    }

    bool dfs(int node,vector<vector<int>>&g, vector<int>&state )
    {
        state[node] = 1;
        bool hasCylcle = false;

        for( int neighbour : g[node] )
        {
            if( state[neighbour] == 0 )
            {
               hasCylcle|= dfs(neighbour,g, state);
            }
            else if(state[neighbour] == 1)
            {
                hasCylcle = true;
            }
        }

        state[node] = 2;
        return hasCylcle;
    }
};