WEEK#8 Graph_Course Schedule

Description of the Problem

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<vector<double>> RelationMatrix;
    vector<int> Vertexs;
    int size;
    vector<int> 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<vector<double>> 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<pair<int, int>>& 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<bool> Visited;
        Visited.resize(RelationMatrix.size());
        while (1) {
            bool end = false;
            int CurrentVertex;
            vector<bool> 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;
    }