# Non-Recursive DSF version for CPP, 29 ms

• ``````//
//  course_schedule.cpp
//  LeeteCodeOJ#207
//
//  Created by Wang Yi on 28/11/16.
//

#include <stack>
#include <queue>
#include <vector>
#include <unordered_set>

using std::stack;
using std::queue;
using std::vector;
using std::unordered_set;

typedef pair<int, int> Val;
typedef vector<unordered_set<int>> Graph;

#define FOR(s, e) \
for (s = 0; s < e; s++) {
#define END ;}

typedef struct _node {
int val;
// int depth;
struct _node * parent;
} node;

class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<int> outdepth(numCourses, 0);
unordered_set<int> vex;
if ((int) prerequisites.size() == 0 || numCourses == 0)
return true;
vector<unordered_set<int>> graph = to_neighbor_repr(numCourses, prerequisites, outdepth);

return dsf(numCourses, graph, outdepth);
}

vector<unordered_set<int>> to_neighbor_repr(int numOfvex, vector<Val>& edges,
vector<int>& outdepth) {
// std::cout << "building ... " << std::endl;
vector<unordered_set<int>> graph(numOfvex);
for (auto edge : edges) {
graph[edge.second].insert(edge.first); // second -> first
outdepth[edge.second]++;
// std::cout << edge.first << " <- " << edge.second << std::endl;
}

return graph;

}

bool dsf(int numOfvex, vector<unordered_set<int>>& graph, vector<int>& outdepth)
{
// preparation
stack<node> s;
vector<bool> visited(numOfvex, false);
vector<bool> onpath(numOfvex, false);
vector<int>  starts;

int i;
node nd;

unordered_set<int> children;

FOR(i, numOfvex)
if (outdepth[i] !=0 ) {
starts.push_back(i);
}
END

if ((int)starts.size() == 0)
return false; // no vertex with indepth of 0 found, a circle found

for (auto j: starts) {
// do dsf search, if not visited
// when a circle in a path found, return false.
// else return true
if (visited[j])
continue;

// non-recursive search
while (!s.empty()) {
node* curr = &(s.top());

if (visited[curr->val]) {
// all children have been read
s.pop();
onpath[curr->val] = false;
continue; // ignore ...
}

onpath[curr->val] = visited[curr->val]= true;
children = graph[curr->val];

if ((int)children.size() == 0) {
s.pop();
onpath[curr->val] = false;

continue;
}

for (auto child: children) {
if (onpath[child]) {
/*
std::cout << std::endl << "a circle found:" << std::endl;
std::cout << child << " <- ";
while (curr->parent != NULL) {
std::cout << curr->val << " <- ";
curr = curr->parent;
}
std::cout << curr->val << std::endl;
*/
return false; // a circle found, might print debug here
}
if (visited[child]) continue;

nd.val = child;
// nd.depth = curr->depth+1;
nd.parent = curr; // for debug purpose ...
s.push(nd);
}
// std::cout << std::endl;
}

} // end of for
return true;
}

};
``````

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