# Summary-of-2-different-implementations

• First of all, this problem is graph-based-topological-sorting problem, so we should consider how to represent graph in C++ code.

After seeing many posts, most of them use the

``````  vector<unordered_set<int>> graph
``````

then we initialize the graph based on all the edges. like this

``````   matrix[node1].insert(node2)
``````

We construct a neighbor-set-based-graph-representation.

Next, we should count all the in-degree of all the vertex.

So , we find the topological-order by deleting the node-that-in-degree=0

Then, update all the related nodes' in-degree.

simple-loop-based-solution

Implementation

``````class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<unordered_set<int>> matrix(numCourses, unordered_set<int>());
/*** construct the directed graph : (1, 0) means edge:0->1  ***/
for(int i=0; i<prerequisites.size(); i++)
matrix[prerequisites[i].second].insert(prerequisites[i].first);
/*** statistic all the in-degree of all the vertex ***/
vector<int> d(numCourses, 0);
for(int i=0; i<numCourses; i++)
for(auto it = matrix[i].begin(); it!=matrix[i].end(); it++){
d[*it]++;
}

/*** topological sort ***/
for(int j=0, i; j<numCourses; ++j){
/*** find the node with in-degree=0 ***/
for(i=0; i<numCourses && d[i]!=0; i++);
if(i==numCourses)   return false;
d[i]=-1;  /*** set d[i]=-1 means delete the node ***/
for(auto it=matrix[i].begin(); it!=matrix[i].end(); it++) d[*it]--;
}
return true;
}
};
``````

In fact, I do not really understand the DFS implementations as others' post

I even can not AC by DFS !

https://leetcode.com/discuss/42543/18-22-lines-c-bfs-dfs-solutions

UPDATE

THe DFS solution is a bit tricky ....

It is based on the idea of the DFS traversal of the graph ..

Here is the AC version refered to jianchao.li.fighter....

``````class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
vector<bool> onpath(numCourses, false), visited(numCourses, false);
for (int i = 0; i < numCourses; i++)
if (!visited[i] && dfs_cycle(graph, i, onpath, visited))
return false;
return true;
}
private:
vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<unordered_set<int>> graph(numCourses);
for (auto pre : prerequisites)
graph[pre.second].insert(pre.first);
return graph;
}
bool dfs_cycle(vector<unordered_set<int>>& graph, int node, vector<bool>& onpath, vector<bool>& visited) {
if (visited[node]) return false;
onpath[node] = visited[node] = true;
for (int neigh : graph[node])
if (onpath[neigh] || dfs_cycle(graph, neigh, onpath, visited))
return true;
return onpath[node] = false;
}
};``````

• Implementation by myself.

My bug happen when I compute the in-degree-array-of-the-graph and the position to find the in-degree=0 pointer.

``````   class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<unordered_set<int>> graph(numCourses, unordered_set<int>());
for(int i=0; i<prerequisites.size(); i++)
graph[prerequisites[i].second].insert(prerequisites[i].first);
vector<int> in_degree(numCourses, 0);
for(int i=0; i<graph.size(); i++)
for(auto it:graph[i])
in_degree[it]++;

int count=0;
for(int i=0; i<numCourses; i++){
int j;
for(j=0; j<numCourses; j++) if(in_degree[j]==0)  break;
if(j==numCourses)   return false;
in_degree[j]=-1;
for(auto it : graph[j])   in_degree[it]--;
}
return true;
}
};``````

• ``````
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<vector<int> > graph(numCourses, vector<int>(0));
vector<int> visit(numCourses, 0);
for (auto a : prerequisites) {
graph[a.second].push_back(a.first);
}
for (int i = 0; i < numCourses; ++i) {
if (!canFinishDFS(graph, visit, i)) return false;
}
return true;
}

bool canFinishDFS(vector<vector<int> > &graph, vector<int> &visit, int i) {
if (visit[i] == -1) return false;
if (visit[i] == 1) return true;
visit[i] = -1;
for (auto a : graph[i]) {
if (!canFinishDFS(graph, visit, a)) return false;
}
visit[i] = 1;
return true;
}
};``````

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