# [C++] Using 3 colored approach

• Here, i have used 3 colored approach. Here w -> represent white means vertex yet not visited.
g -> gray , it means it is under DFS recursion and we again found the same node. This means cycle exists and return false.
b -> black node when DFS is done visiting the node.
This method checks cycle as well as keeps storing answer in stack in case cycle doesn't exists.

``````class Graph {
public:
int v;
Graph(int v)
{
this->v=v;
}
void addedges(int src , int dest)
{
}
};
class Solution {
public:
stack <int> st;
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
Graph g(numCourses);
for (int i=0 ; i < prerequisites.size() ; i++)
vector <int> ans;
if(!courseScheduleCheck(g))
return ans;
while(!st.empty())
{
ans.push_back(st.top());
st.pop();
}
return ans;
}
bool courseScheduleCheck(Graph g)
{
int v = g.v;
vector <char> visit(v,'w');
for(int i=0 ; i<v;i++)
{
if(visit[i]== 'w')
if(iscycle(g,i,visit))
return false;
}
return true;
}
bool iscycle(Graph g , int i, vector <char> & visit)
{
list <int> ::iterator it;
{
if(visit[*it]== 'g')
return true;
else
{
if(visit[*it] != 'b')
{
visit[*it] = 'g';
if(iscycle(g,*it,visit))
return true;
}
}
}
visit[i]='b';
st.push(i);
return false;
}
};``````

• Awesome solution! Innovative use of topological sort for detecting deadlock.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.