Given n courses labeled from 0 to n - 1, and an array prerequisites[][] where prerequisites[i] = [x, y] indicates that you must take course y before taking course x.
Return true if it is possible to complete all courses, otherwise return false.
Examples:
Input: n = 4, prerequisites[][] = [[2, 0], [2, 1], [3, 2]]
Output: true
Explanation: To take course 2, you must first finish courses 0 and 1.
To take course 3, you must first finish course 2.
All courses can be completed, for example in the order [0, 1, 2, 3] or [1, 0, 2, 3].Input: n = 3, prerequisites[][] = [[0, 1], [1, 2], [2, 0]]
Output: false
Explanation: To take course 0, you must first finish course 1.
To take course 1, you must first finish course 2.
To take course 2, you must first finish course 0.
Since each course depends on the other, it is impossible to complete all courses.
Try it on GfG Practice
Table of Content
[Approach 1] - Using DFS for Cycle Detection
The idea is to represent the courses and their prerequisites as a directed graph, where each course is a vertex. For each prerequisite [x, y], since course y must be completed before course x, we add a directed edge from y to x. If the graph contains a cycle, it means some courses depend on each other in a loop, making it impossible to complete all courses. If there is no cycle, a valid order exists to finish all courses.
For more details, refer to Cycle Detection using DFS in Directed Graph.
//Driver Code Starts
#include <iostream>
#include <vector>
using namespace std;
//Driver Code Ends
// DFS to detect cycle
bool dfs(int node, vector<vector<int>>& adj, vector<int>& visited) {
// mark as visiting
visited[node] = 1;
for (int neighbor : adj[node]) {
if (visited[neighbor] == 1) {
// cycle detected
return false;
} else if (visited[neighbor] == 0) {
if (!dfs(neighbor, adj, visited)) {
return false;
}
}
}
// mark as visited
visited[node] = 2;
return true;
}
// Function to check if all courses can be completed
bool canFinish(int n, vector<vector<int>>& prerequisites) {
vector<vector<int>> adj(n);
for (auto& pre : prerequisites) {
int dest = pre[0];
int src = pre[1];
adj[src].push_back(dest);
}
// 0 = unvisited, 1 = visiting, 2 = visited
vector<int> visited(n, 0);
for (int i = 0; i < n; i++) {
if (visited[i] == 0) {
if (!dfs(i, adj, visited)) {
// cycle detected
return false;
}
}
}
return true;
}
//Driver Code Starts
int main() {
int n = 4;
vector<vector<int>> prerequisites = { {2, 0}, {2, 1}, {3, 2} };
cout << (canFinish(n, prerequisites) ? "true" : "false") << endl;
return 0;
}
//Driver Code Ends
//Driver Code Starts
import java.util.ArrayList;
class GfG {
//Driver Code Ends
// DFS to detect cycle
static boolean dfs(int node, ArrayList<ArrayList<Integer>> adj, int[] visited) {
// mark as visiting
visited[node] = 1;
for (int neighbor : adj.get(node)) {
if (visited[neighbor] == 1) {
// cycle detected
return false;
} else if (visited[neighbor] == 0) {
if (!dfs(neighbor, adj, visited)) {
return false;
}
}
}
// mark as visited
visited[node] = 2;
return true;
}
// Function to check if all courses can be completed
static boolean canFinish(int n, int[][] prerequisites) {
ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (int[] pre : prerequisites) {
int dest = pre[0];
int src = pre[1];
adj.get(src).add(dest);
}
// 0 = unvisited, 1 = visiting, 2 = visited
int[] visited = new int[n];
for (int i = 0; i < n; i++) {
if (visited[i] == 0) {
if (!dfs(i, adj, visited)) {
// cycle detected
return false;
}
}
}
return true;
}
//Driver Code Starts
public static void main(String[] args) {
int n = 4;
int[][] prerequisites = { {2, 0}, {2, 1}, {3, 2} };
System.out.println(canFinish(n, prerequisites) ? "true" : "false");
}
}
//Driver Code Ends
#Driver Code Starts
from typing import List
#Driver Code Ends
# DFS to detect cycle
def dfs(node, adj, visited):
# mark as visiting
visited[node] = 1
for neighbor in adj[node]:
if visited[neighbor] == 1:
# cycle detected
return False
elif visited[neighbor] == 0:
if not dfs(neighbor, adj, visited):
return False
# mark as visited
visited[node] = 2
return True
# Function to check if all courses can be completed
def canFinish(n, prerequisites) -> bool:
adj = [[] for _ in range(n)]
for dest, src in prerequisites:
adj[src].append(dest)
# 0 = unvisited, 1 = visiting, 2 = visited
visited = [0] * n
for i in range(n):
if visited[i] == 0:
if not dfs(i, adj, visited):
# cycle detected
return False
return True
#Driver Code Starts
if __name__ == "__main__":
n = 4
prerequisites = [[2, 0], [2, 1], [3, 2]]
print("true" if canFinish(n, prerequisites) else "false")
#Driver Code Ends
//Driver Code Starts
using System;
using System.Collections.Generic;
class GfG {
//Driver Code Ends
// DFS to detect cycle
static bool dfs(int node, List<List<int>> adj, int[] visited) {
// mark as visiting
visited[node] = 1;
foreach (int neighbor in adj[node]) {
if (visited[neighbor] == 1) {
// cycle detected
return false;
}
else if (visited[neighbor] == 0) {
if (!dfs(neighbor, adj, visited)) {
return false;
}
}
}
// mark as visited
visited[node] = 2;
return true;
}
// Function to check if all courses can be completed
static bool canFinish(int n, int[,] prerequisites) {
List<List<int>> adj = new List<List<int>>();
for (int i = 0; i < n; i++) {
adj.Add(new List<int>());
}
int m = prerequisites.GetLength(0);
for (int i = 0; i < m; i++) {
int dest = prerequisites[i, 0];
int src = prerequisites[i, 1];
adj[src].Add(dest);
}
// 0 = unvisited, 1 = visiting, 2 = visited
int[] visited = new int[n];
for (int i = 0; i < n; i++) {
if (visited[i] == 0) {
if (!dfs(i, adj, visited)) {
// cycle detected
return false;
}
}
}
return true;
}
//Driver Code Starts
public static void Main(string[] args) {
int n = 4;
int[,] prerequisites = { {2, 0}, {2, 1}, {3, 2} };
Console.WriteLine(canFinish(n, prerequisites) ? "true" : "false");
}
}
//Driver Code Ends
// DFS to detect cycle
function dfs(node, adj, visited) {
// mark as visiting
visited[node] = 1;
for (let neighbor of adj[node]) {
if (visited[neighbor] === 1) {
// cycle detected
return false;
} else if (visited[neighbor] === 0) {
if (!dfs(neighbor, adj, visited)) {
return false;
}
}
}
// mark as visited
visited[node] = 2;
return true;
}
// Function to check if all courses can be completed
function canFinish(n, prerequisites) {
let adj = Array.from({ length: n }, () => []);
for (let pre of prerequisites) {
let dest = pre[0];
let src = pre[1];
adj[src].push(dest);
}
// 0 = unvisited, 1 = visiting, 2 = visited
let visited = Array(n).fill(0);
for (let i = 0; i < n; i++) {
if (visited[i] === 0) {
if (!dfs(i, adj, visited)) {
// cycle detected
return false;
}
}
}
return true;
}
//Driver Code Starts
// Driver Code
const n = 4;
const prerequisites = [[2, 0], [2, 1], [3, 2]];
console.log(canFinish(n, prerequisites) ? 'true' : 'false');
//Driver Code Ends
Output
true
Time Complexity: O(V+E), where V is the number of vertices and E is the number of edges.
Auxiliary Space: O(V+E)
[Approach 2] - Using Topological Sorting
The idea is to represent the courses and their prerequisites as a directed graph, where each course is a vertex. For each prerequisite [x, y], since course y must be completed before course x, we add a directed edge from y to x. By performing a topological sort, we can determine whether it is possible to complete all courses. If all courses are visited, there is no cycle and all courses can be completed. If any course remains unvisited, it means there is a cycle, where courses depend on each other in a loop, making it impossible to finish all of them.
//Driver Code Starts
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
//Driver Code Ends
bool canFinish(int n, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(n);
vector<int> inDegree(n, 0);
for (auto& pre : prerequisites) {
int dest = pre[0];
int src = pre[1];
graph[src].push_back(dest);
inDegree[dest]++;
}
queue<int> q;
// Push all the nodes with no dependencies
// (indegree = 0)
for (int i = 0; i < n; i++)
if (inDegree[i] == 0)
q.push(i);
while (!q.empty()) {
int node = q.front(); q.pop();
for (int child : graph[node]) {
inDegree[child]--;
// Push the neighboring node if we have covered
// all its dependencies (indegree = 0)
if (inDegree[child] == 0)
q.push(child);
}
}
// Check if there is a node whose indegree is not zero
for (int i = 0; i < n; i++)
if (inDegree[i] != 0)
return false;
return true;
}
//Driver Code Starts
int main() {
int n = 4;
vector<vector<int>> prerequisites = { {2, 0}, {2, 1}, {3, 2} };
cout << (canFinish(n, prerequisites) ? "true" : "false") << endl;
return 0;
}
//Driver Code Ends
//Driver Code Starts
import java.util.ArrayList;
import java.util.List;
import java.util.LinkedList;
import java.util.Queue;
class GfG {
//Driver Code Ends
static boolean canFinish(int n, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
int[] inDegree = new int[n];
for (int i = 0; i < n; i++)
graph.add(new ArrayList<>());
for (int[] pre : prerequisites) {
int dest = pre[0];
int src = pre[1];
graph.get(src).add(dest);
inDegree[dest]++;
}
Queue<Integer> q = new LinkedList<>();
// Push all the nodes with no dependencies (indegree = 0)
for (int i = 0; i < n; i++)
if (inDegree[i] == 0)
q.add(i);
while (!q.isEmpty()) {
int node = q.poll();
for (int child : graph.get(node)) {
inDegree[child]--;
// Push the neighboring node if
// we have covered all its dependencies (indegree = 0)
if (inDegree[child] == 0)
q.add(child);
}
}
// Check if there is a node whose indegree is not zero
for (int i = 0; i < n; i++)
if (inDegree[i] != 0)
return false;
return true;
}
//Driver Code Starts
public static void main(String[] args) {
int n = 4;
int[][] prerequisites = { {2, 0}, {2, 1}, {3, 2} };
System.out.println(canFinish(n, prerequisites) ? "true" : "false");
}
}
//Driver Code Ends
#Driver Code Starts
from collections import deque
#Driver Code Ends
def canFinish(n, prerequisites):
graph = [[] for _ in range(n)]
inDegree = [0] * n
for dest, src in prerequisites:
graph[src].append(dest)
inDegree[dest] += 1
q = deque()
# Push all the nodes with no dependencies (indegree = 0)
for i in range(n):
if inDegree[i] == 0:
q.append(i)
while q:
node = q.popleft()
for child in graph[node]:
inDegree[child] -= 1
# Push the neighboring node
# if we have covered all its dependencies (indegree = 0)
if inDegree[child] == 0:
q.append(child)
# Check if there is a node whose indegree is not zero
for i in range(n):
if inDegree[i] != 0:
return False
return True
#Driver Code Starts
if __name__ == '__main__':
n = 4
prerequisites = [[2, 0], [2, 1], [3, 2]]
print("true" if canFinish(n, prerequisites) else "false")
#Driver Code Ends
//Driver Code Starts
using System;
using System.Collections.Generic;
//Driver Code Ends
class GfG {
static bool canFinish(int n, int[,] prerequisites) {
List<List<int>> graph = new List<List<int>>();
int[] inDegree = new int[n];
for (int i = 0; i < n; i++)
graph.Add(new List<int>());
int m = prerequisites.GetLength(0);
for (int i = 0; i < m; i++) {
int dest = prerequisites[i, 0];
int src = prerequisites[i, 1];
graph[src].Add(dest);
inDegree[dest]++;
}
Queue<int> q = new Queue<int>();
// Push all the nodes with no dependencies (indegree = 0)
for (int i = 0; i < n; i++)
if (inDegree[i] == 0)
q.Enqueue(i);
while (q.Count > 0) {
int node = q.Dequeue();
foreach (int child in graph[node]) {
inDegree[child]--;
// Push the neighboring node if all dependencies are covered
if (inDegree[child] == 0)
q.Enqueue(child);
}
}
// Check if there is a node whose indegree is not zero
for (int i = 0; i < n; i++)
if (inDegree[i] != 0)
return false;
return true;
}
//Driver Code Starts
public static void Main() {
int n = 4;
int[,] prerequisites = { {2, 0}, {2, 1}, {3, 2} };
Console.WriteLine(canFinish(n, prerequisites) ? "true" : "false");
}
}
//Driver Code Ends
function canFinish(n, prerequisites) {
const graph = Array.from({ length: n }, () => []);
const inDegree = Array(n).fill(0);
for (const [dest, src] of prerequisites) {
graph[src].push(dest);
inDegree[dest]++;
}
const q = [];
// Push all nodes with indegree = 0
for (let i = 0; i < n; i++)
if (inDegree[i] === 0)
q.push(i);
let front = 0;
while (front < q.length) {
const node = q[front++];
for (const child of graph[node]) {
inDegree[child]--;
// Push if all dependencies are resolved
if (inDegree[child] === 0)
q.push(child);
}
}
// Check if any node still has indegree > 0
for (let i = 0; i < n; i++)
if (inDegree[i] !== 0)
return false;
return true;
}
//Driver Code Starts
// Driver code
const n = 4;
const prerequisites = [[2, 0], [2, 1], [3, 2]];
console.log(canFinish(n, prerequisites) ? "true" : "false");
//Driver Code Ends
Output
true
Time Complexity: O(V+E), where V is the number of vertices and E is the number of edges.
Auxiliary Space: O(V)