# 484 ms C++ solutions using topological sort/DFS

• ``````bool find_cycle(int *arr,vector<int> *v, int source, vector<int> *topo_sort)
{
if(arr[source]==1)
return true;

int size = v[source].size(), end_vertice;
int ret_val = false;
vector<int>::iterator v_itr = v[source].begin();

//  cout << "Processing vertic : " << source << endl;
arr[source]=1;

while(v_itr!=v[source].end())
{
end_vertice = *v_itr;
// cout << "Pre req ver # " << *v_itr << " with value = " <<arr[end_vertice] << endl;

if(arr[end_vertice]==1)
return true;
else if(arr[end_vertice]==0)
{
//cout << "Going to other node of req req vertic : " << end_vertice <<endl;
ret_val = (ret_val || (find_cycle(arr,v,*v_itr,topo_sort)));
}
v_itr++;
}
arr[source]=2;
topo_sort->push_back(source);

return ret_val;
}

vector<int> findOrder(int numCourses, vector<pair<int, int> >& prerequisites)
{
int *arr = (int *)malloc(sizeof(int)*numCourses);
for(int i=0;i<numCourses;i++)
arr[i] = 0;

// convert the vector into
vector<int> course_list[numCourses+1];
vector<pair<int, int> >::iterator pre_itr;
pair<int,int> temp_pair;
pre_itr = prerequisites.begin();

int start_ver, dest_ver;

while(pre_itr!= prerequisites.end())
{
temp_pair = *pre_itr;
start_ver = temp_pair.first;
dest_ver = temp_pair.second;
course_list[start_ver].push_back(dest_ver);
pre_itr++;
}

vector<int> topo_sort;
vector<int> empty_vector;
bool cycle_found=false;

for(int i=0;i<numCourses;i++)
if(arr[i]==0)
if(find_cycle(arr,course_list,i,&topo_sort))
cycle_found=true;

//reverse(topo_sort.begin(),topo_sort.end());
if(cycle_found)
return empty_vector;
else