# Three intuitive topological methods enclosed with a DFS in cpp

• ``````class Solution
{
private:
bool isCycled(const vector<vector<int>>& graph, int label, vector<bool>& visited, vector<bool>& in_path)
{
if(visited[label]) return false; //avoid re-checking the nodes visited in previous paths;
visited[label] = true; //each node visited should be labelled as visited avoiding further checking;
in_path[label] = true; //should be labelled as visited for the current path;
for(int neighbor: graph[label])
if(in_path[neighbor] || isCycled(graph, neighbor, visited, in_path)) return true;
in_path[label] = false; //restored to its unvisited state for another branch of the same starting node;
return false;
}
public:
//AC - 24ms - DFS method;
bool canFinish(int num, vector<pair<int, int>> pres)
{
vector<vector<int>> graph(num);
for(auto& pair: pres)
graph[pair.second].push_back(pair.first);
vector<bool> visited(num, false), in_path(num, false);
for(int i = 0; i < num; i++)
if(!visited[i] && isCycled(graph, i, visited, in_path)) return false;
return true;
}

//AC - 320ms - topological sorting method;
bool canFinish(int num, vector<pair<int, int>> pres)
{
unordered_map<int, vector<int>> graph;
vector<int> indegrees(num, 0);
for(auto& pair: pres)
{
graph[pair.second].push_back(pair.first);
indegrees[pair.first]++;
}
while(graph.size())
{
int i = 0;
for(; i < num; i++)
if(graph.count(i) && indegrees[i]==0) break;
if(i == num) return false;
for(int neigh: graph[i])
indegrees[neigh]--;
graph.erase(i);
}
return true;
}
};``````

• Topological method can be further optimised in this special problem using vector instead of map.

``````class Solution
{
public:
//AC - 36ms - using vector instead of unordered_map to accelerate;
bool canFinish(int num, vector<pair<int, int>> pres)
{
vector<vector<int>> graph(num);
vector<int> indegrees(num, 0);
for(auto& pair: pres)
{
graph[pair.second].push_back(pair.first);
indegrees[pair.first]++;
}
for(int  j = 0; j < num; j++)
{
int i = 0;
for(; i < num; i++)
if(!indegrees[i]) break;
indegrees[i] = -1; //avoid re-checking;
if(i == num) return false;
for(int neigh: graph[i])
indegrees[neigh]--;
}
return true;
}
};``````

• Actually using BFS and topological method can be the fastest, so there it is.

``````class Solution {
public:
//AC - 20ms;
bool canFinish(int num, vector<pair<int, int>>& pres) {
vector<vector<int>> graph(num);
vector<int> indegrees(num, 0);
queue<int> toVisit;
int count = 0;
for(auto& pair: pres)
{
graph[pair.second].push_back(pair.first);
indegrees[pair.first]++;
}
for(int i = 0; i < num; i++)
if(!indegrees[i]) toVisit.push(i);
while(!toVisit.empty())
{
int start = toVisit.front();
toVisit.pop();
for(auto n: graph[start])
if(--indegrees[n] == 0) toVisit.push(n);
count++;
}
return count==num;
}
};``````

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