|
You have to complete n courses. There are m requirements of form “course a has to be completed before course b”. Your task is to find an order in which you can complete the courses.
Examples:
Input: n = 5, m = 3, requirements[][] = {{1, 2}, {3, 1}, {4, 5}}
Output: 3 4 1 5 2
Explanation:
- Since course 3 and 4 have no requirements, we can complete course 3 and 4.
- After completing course 3, we can complete course 1.
- After completing course 4, we can complete course 5.
- After completing course 1, we can complete course 2.
Input: n = 4, m = 2, requirements[][] = {{4, 2}, {3, 1}}
Output: 3 4 1 2
Explanation:
- Since course 3 and 4 have on requirements, we can complete course 3 and 4.
- After completing course 3, we can complete course 1.
- After completing course 4, we can complete course 2.
Approach: To solve the problem, follow the below idea:
The problem can be solved using Topological Sort. Each course can be considered as a node and each requirement (a, b) can be considered as a directed edge from node a to node b. Now, we can find the topological sort of the graph to find the order in which courses can be completed.
Step-by-step approach:
- Construct a graph of N nodes for N courses.
- For every requirement, draw directed edges between the nodes and keep track of the indegree of each node.
- Maintain a queue to keep track of nodes which we can visit next.
- Push all the nodes with indegree 0 into the queue.
- Till queue is not empty,
- Pop the node at the front of the queue and push it into the ans vector.
- Decrease the indegree of all the neighboring nodes by 1.
- If the indegree of neighboring node becomes 0, push the neighboring node to the queue.
- After the queue becomes empty, print the ans vector as the final answer.
Below is the implementation of the algorithm:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to perform topological sort and find the order
// in which courses can be completed
vector<int> solve(int n, vector<vector<int> >& adj,
vector<int>& indeg)
{
queue<int> q;
vector<int> ans;
// Initialize queue with nodes having in-degree 0
for (int i = 1; i <= n; ++i) {
if (indeg[i] == 0)
q.push(i);
}
// Iterate till q is not empty
while (!q.empty()) {
// Pop the front node of the queue
int node = q.front();
q.pop();
// Push the front node to the answer
ans.push_back(node);
// Update in degree of adjacent nodes
for (int child : adj[node]) {
indeg[child] -= 1;
if (indeg[child] == 0) {
q.push(child);
}
}
}
return ans;
}
int main()
{
int n, m;
// Sample input
n = 5;
m = 3;
vector<pair<int, int> > requirements
= { { 1, 2 }, { 3, 1 }, { 4, 5 } };
vector<vector<int> > graph(n + 1);
vector<int> indeg(n + 1, 0);
// Build directed graph and calculate in-degrees
for (int i = 0; i < m; ++i) {
int u = requirements[i].first;
int v = requirements[i].second;
graph[u].push_back(v);
indeg[v] += 1;
}
// Get the topological sort
vector<int> ans = solve(n, graph, indeg);
// Print the result
if (ans.size() != n) {
cout << "IMPOSSIBLE";
}
else {
for (int i = 0; i < n; i++)
cout << ans[i] << " ";
}
return 0;
}
import java.util.*;
public class CourseSchedule {
// Function to perform topological sort and find the
// order in which courses can be completed
public static List<Integer>
solve(int n, List<List<Integer> > adj, int[] indeg)
{
Queue<Integer> q = new LinkedList<>();
List<Integer> ans = new ArrayList<>();
// Initialize queue with nodes having in-degree 0
for (int i = 1; i <= n; ++i) {
if (indeg[i] == 0) {
q.add(i);
}
}
// Iterate till q is not empty
while (!q.isEmpty()) {
// Pop the front node of the queue
int node = q.poll();
// Push the front node to the answer
ans.add(node);
// Update in-degree of adjacent nodes
for (int child : adj.get(node)) {
indeg[child] -= 1;
if (indeg[child] == 0) {
q.add(child);
}
}
}
return ans;
}
public static void main(String[] args)
{
int n, m;
// Sample input
n = 5;
m = 3;
List<int[]> requirements = Arrays.asList(
new int[] { 1, 2 }, new int[] { 3, 1 },
new int[] { 4, 5 });
List<List<Integer> > graph = new ArrayList<>(n + 1);
for (int i = 0; i <= n; ++i) {
graph.add(new ArrayList<>());
}
int[] indeg = new int[n + 1];
// Build directed graph and calculate in-degrees
for (int[] req : requirements) {
int u = req[0];
int v = req[1];
graph.get(u).add(v);
indeg[v] += 1;
}
// Get the topological sort
List<Integer> ans = solve(n, graph, indeg);
// Print the result
if (ans.size() != n) {
System.out.println("IMPOSSIBLE");
}
else {
for (int i = 0; i < n; ++i) {
System.out.print(ans.get(i) + " ");
}
}
}
}
// This code is contributed by shivamgupta0987654321
from collections import deque, defaultdict
# Function to perform topological sort and find the order
# in which courses can be completed
def solve(n, adj, indeg):
q = deque()
ans = []
# Initialize queue with nodes having in-degree 0
for i in range(1, n + 1):
if indeg[i] == 0:
q.append(i)
# Iterate till q is not empty
while q:
# Pop the front node of the queue
node = q.popleft()
# Push the front node to the answer
ans.append(node)
# Update in degree of adjacent nodes
for child in adj[node]:
indeg[child] -= 1
if indeg[child] == 0:
q.append(child)
return ans
def main():
# Sample input
n = 5
m = 3
requirements = [(1, 2), (3, 1), (4, 5)]
graph = defaultdict(list)
indeg = [0] * (n + 1)
# Build directed graph and calculate in-degrees
for u, v in requirements:
graph[u].append(v)
indeg[v] += 1
# Get the topological sort
ans = solve(n, graph, indeg)
# Print the result
if len(ans) != n:
print("IMPOSSIBLE")
else:
print(" ".join(map(str, ans)))
if __name__ == "__main__":
main()
# This code is contributed by Ayush Mishra
class CourseSchedule {
// Function to perform topological sort and find the
// order in which courses can be completed
static solve(n, adj, indeg) {
let q = [];
let ans = [];
// Initialize queue with nodes having in-degree 0
for (let i = 1; i <= n; ++i) {
if (indeg[i] === 0) {
q.push(i);
}
}
// Iterate till q is not empty
while (q.length !== 0) {
// Pop the front node of the queue
let node = q.shift();
// Push the front node to the answer
ans.push(node);
// Update in-degree of adjacent nodes
for (let child of adj[node]) {
indeg[child] -= 1;
if (indeg[child] === 0) {
q.push(child);
}
}
}
return ans;
}
static main() {
let n, m;
// Sample input
n = 5;
m = 3;
let requirements = [
[ 1, 2 ], [ 3, 1 ], [ 4, 5 ]
];
let graph = new Array(n + 1).fill(null).map(() => []);
let indeg = new Array(n + 1).fill(0);
// Build directed graph and calculate in-degrees
for (let req of requirements) {
let u = req[0];
let v = req[1];
graph[u].push(v);
indeg[v] += 1;
}
// Get the topological sort
let ans = CourseSchedule.solve(n, graph, indeg);
// Print the result
if (ans.length !== n) {
console.log("IMPOSSIBLE");
} else {
console.log(ans.join(" "));
}
}
}
// Call the main function
CourseSchedule.main();
Time Complexity: O(N)
Auxiliary Space: O(N)
|
