WEEK#8|WEEK#8 Graph_Course Schedule WEEK#8Graph_CourseSchedule

Description of the Problem
【WEEK#8|WEEK#8 Graph_Course Schedule】There are a total of n courses you have to take, labeled from 0
to n - 1
.
Some courses may have prerequisites, for example, to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.
Thinking Process
Obviously this is a problem of detecting the existence of circle in a graph.
TLE Solution (35 / 37 test cases passed.)
TLE when size surpasses 2000

class Graph { private: vector> RelationMatrix; vector Vertexs; int size; vector TopSort_Vertexs; public: Graph(int n) { Vertexs.resize(n); size = n; RelationMatrix.resize(n); for (int i = 0; i < RelationMatrix.size(); i++) RelationMatrix[i].resize(n); }void AddEdge(int vertex1, int vertex2, double length) { RelationMatrix[vertex1][vertex2] = length; }bool TopologicalSort() { vector> RM = RelationMatrix; while (1) { bool FindNothing = true; for (int i = 0; i < size; i++) { bool flag = true; for (int j = 0; j < size; j++) { if (RM[j][i] == 1 || RM[0][i] == -1) { flag = false; break; } } if (flag) { TopSort_Vertexs.push_back(i); FindNothing = false; for (int k = 0; k < size; k++) if (RM[i][k] != -1) RM[i][k] = 0; RM[0][i] = -1; // delete i; } } if (FindNothing || TopSort_Vertexs.size() == size) break; } if (TopSort_Vertexs.size() == size) return true; return false; }void AddConnectedEdge() { for (int i = 0; i < Vertexs.size(); i++) { for (int j = 0; j < Vertexs.size(); j++) { for (int k = 0; k < Vertexs.size(); k++) { if (RelationMatrix[i][k] != -1 && RelationMatrix[k][j] != -1) { RelationMatrix[i][j] = RelationMatrix[i][k] * RelationMatrix[k][j]; RelationMatrix[j][i] = 1 / (RelationMatrix[i][k] * RelationMatrix[k][j]); } } } } }void SetVertexs(string v) { Vertexs.resize(v.length()); }double GetLength(int vertex1, int vertex2) { return RelationMatrix[vertex1][vertex2]; } }; class Solution { public: bool canFinish(int numCourses, vector>& prerequisites) { Graph * graph = new Graph(numCourses); for (auto i : prerequisites) { graph->AddEdge(i.second, i.first, 1); } return graph->TopologicalSort(); } };

Incomplete DFS Solution (quick enough but unable to handle specific cases)
unable to detect circle in 1<-0->2->0

bool DFS() { vector Visited; Visited.resize(RelationMatrix.size()); while (1) { bool end = false; int CurrentVertex; vector CurrentlyVisiting; CurrentlyVisiting.clear(); CurrentlyVisiting.resize(RelationMatrix.size()); for (int i = 0; i < RelationMatrix.size(); i++) { // find a unvisited vertex bool found = true; if (Visited[i] == 1) continue; /*for (int j = 0; j < RelationMatrix.size(); j++) { if (RelationMatrix[j][i] != 0) { // find a indegree = 0 vertex found = false; break; } }*/ if (found) { Visited[i] = 1; CurrentlyVisiting[i] = 1; CurrentVertex = i; break; } if (i == RelationMatrix.size() - 1) { // unvisited vertex not found, end while end = true; break; } } if (end) break; while (1) { // unvisited vertex found, begin DFS bool whilebreak = false; for (int i = 0; i < RelationMatrix.size(); i++) { bool visitNext = false; if (i != CurrentVertex) if (RelationMatrix[CurrentVertex][i] != 0) { if (CurrentlyVisiting[i] == 1) // Circle detected, return false return false; if (Visited[i] == 0) { Visited[i] = 1; CurrentlyVisiting[i] = 1; CurrentVertex = i; visitNext = true; } } if (visitNext) break; if (i == RelationMatrix.size() - 1) // can't find an unvisited vertex to go to, break to find a new vertex whilebreak = true; } if (whilebreak) break; } bool flag = false; for (int i = 0; i < RelationMatrix.size(); i++) if (Visited[i] == false) { flag = true; break; } if (flag) continue; else break; // all vertexes visited , end ; } for (int i = 0; i < Visited.size(); i++) if (Visited[i] == 0) return false; return true; }