Easy to understand solution - perform a search from each node


  • 0
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            // Represent the graph as adjacency list so we can easily traverse it.
            vector<vector<int> > adjacencyList(numCourses, vector<int>());
            for (pair<int, int> edge : prerequisites) {
                adjacencyList[edge.first].push_back(edge.second);
            }
    
            // Perform Depth-first-search from each node and try to find
            // a cycle.
            vector<bool> visited(numCourses);
            stack<int> dfsStack;
            for (int vertex = 0; vertex < numCourses; ++vertex) {
                fill(visited.begin(), visited.end(), false);
                dfsStack.push(vertex);
                while (!dfsStack.empty()) {
                    int currentVertex = dfsStack.top();
                    dfsStack.pop();
                    for (int neighbor : adjacencyList[currentVertex]) {
                        // Check if we hit the starting vertex then this is a cycle.
                        if (neighbor == vertex) return false;
                        if (visited[neighbor]) continue;
                        visited[neighbor] = true;
                        dfsStack.push(neighbor);
                    }
                }
            }
            return true;
        }
    

Log in to reply
 

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