Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

I want this Lab's C code There are my false example code at the end of my question Lab 9 : Course Registration Description A

I want this Lab's C code
There are my false example code at the end of my question
Lab 9: Course Registration
Description
A newly admitted student must register courses in a way that adheres to prerequisite requirements. A prerequisite is a requirement that one course must be completed before another course can be taken. Each course can have multiple prerequisites, and the prerequisite structure forms a directed acyclic graph. Each course is identified by a unique number from 0 to N-1. The task is to determine if all courses can be successfully registered by the student.
Specific rules include:
prerequisites[i]=[a_i, b_i] means that course b_i must be taken before course a_i.
An algorithm should be designed to determine if it's possible to complete all courses, returning True if possible and False otherwise.
Input
The input provides the total number of courses N and a list of prerequisite pairs. Each pair [a, b] specifies a prerequisite relationship where course b must be completed before course a.
The prerequisite pairs are provided as [[a_0, b_0],[a_1, b_1],...,[a_k, b_k]].
a_i and b_i represent courses identified by their numbers. There are no spaces or tabs in the input.
Output
The output should be either True or False, indicating whether all courses can be registered according to the prerequisites.
Constraints
1<= N <=2000
0<= prerequisites.length <=5000
prerequisites[i].length ==2
0<= a_i, b_i < N
This problem essentially involves checking for cycles in a directed graph to determine if a topological ordering of the courses is possible, which allows all courses to be taken in compliance with the prerequisites.
sample input1
2
[[1,0]]
True
Explanation: Course 0->1 denotes that you must complete course 0 before taking course 1.
sample input 2
2
[[1,0],[0,1]]
False
Explanation: There is a cycle because course 1 must be completed before course 0, and course 0 must be completed before course 1.
sample input3
3
[0,0]
False
Explanation: A course cannot be a prerequisite to itself as it forms an immediate cycle.
#include
#include
#include
using namespace std;
bool canFinish(int numCourses, vector> &prerequisites){
// Graph to hold the list of prerequisites for each course
vector> graph(numCourses);
// Array to track the number of prerequisites (in-degrees) for each course
vector inDegree(numCourses,0);
// Build the graph and count the in-degrees
for (auto &pre : prerequisites){
graph[pre[1]].push_back(pre[0]); // Note the reversal, pre[1] is prerequisite for pre[0]
inDegree[pre[0]]++; // Increment the in-degree of the course that needs pre[1]
}
// Queue for the courses with no prerequisites
queue zeroInDegree;
for (int i =0; i < numCourses; i++){
if (inDegree[i]==0){
zeroInDegree.push(i); // If no prerequisites, it's ready to be taken
}
}
int visited =0; // Counter for the number of courses that can be completed
while (!zeroInDegree.empty()){
int course = zeroInDegree.front();
zeroInDegree.pop();
visited++; // A course can be taken, mark it visited
// Check the courses that depend on the current course
for (int next : graph[course]){
if (--inDegree[next]==0){// If no more prerequisites for this course
zeroInDegree.push(next); // It's ready to be taken
}
}
}
// If we were able to visit all courses, then it's possible to finish
return visited == numCourses;
}
int main(){
int N; // Total number of courses
cin >> N;
vector> prerequisites;
int a, b;
char comma; // To handle the comma in the input
// Read pairs of courses in the format [a, b]
while (cin >> a >> comma >> b){
prerequisites.push_back({a, b});
}
cout <<(canFinish(N, prerequisites)? "True" : "False")<< endl;
return 0;
}

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Secrets Of Analytical Leaders Insights From Information Insiders

Authors: Wayne Eckerson

1st Edition

1935504347, 9781935504344

More Books

Students also viewed these Databases questions