我怎样才能解决这个关于毕业的算法难题

Question

我正在尝试使用 java:

来解决这个编程问题

Description

A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate.

Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall.

For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall.

In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue.

Input

There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 <= n <= 12, which is the number of courses in this data set and m, 2 <= m <= 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered ('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 <= p <= 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above.

Output

The output contains one line for each data set, formatted as shown in the sample output.

Sample Input
4 6
cs123 mt42 cs456 cs789
mt42 F 0
cs123 S 0
cs456 S 2 cs123 mt42
cs789 B 1 cs456
3 6
math1 comp2 comp3
comp3 S 1 comp2
math1 S 0
comp2 F 1 math1
4 3
m10 m20 c33 c44
m10 B 0
m20 B 0
c33 B 0
c44 B 0
-1 -1
Sample Output
The minimum number of semesters required to graduate is 5.
The minimum number of semesters required to graduate is 4.
The minimum number of semesters required to graduate is 2.

我试图使用 java 来解决它，但没有找到继续进行的方法。知道我怎样才能轻松做到这一点。我正在寻找 AC 率是 50%。恐怕我错过了一个简单的方法。这是我的代码：

String output="The minimum number of semesters required to graduate is ";
    Scanner sc=new Scanner(System.in);
    int totalcourse=sc.nextInt();
    int maxcourse=sc.nextInt();
    int semester=0;
    HashMap<String, List<String>> preqcourses=new HashMap<String, List<String>>();
    boolean fall=true;
    ArrayList<String> courses=new ArrayList<String>();
    for(int i=0;i<totalcourse;i++)
    {
        courses.add(sc.next());         
    }
    for(int c=0;c<totalcourse;c++)
    {
        String course=sc.next();
        String osem=sc.next();
        int prereq=sc.nextInt();
        String [] coursearr=new String[prereq];
        //populating prereq course array
        for(int p=0;p<prereq;p++)
        {
            coursearr[p]=sc.next();
        }
        preqcourses.put(course, Arrays.asList(coursearr));  // Adding prerequisite courses to hashmap               
        if(fall)
        {
            if((osem.equals("F")|| osem.equals("B"))&& prereq==0)
            {
                courses.remove(course);

                semester++;
            }
            if((osem.equals("F")|| osem.equals("B"))&& preqcourses.get(course).size()>0)
            {
                for(int q=0;q<preqcourses.get(course).size();q++)
                {
                    if(!courses.contains(preqcourses.get(course).get(q)))
                    {
                        preqcourses.get(course).remove(preqcourses.get(course).get(q));
                        prereq--;
                    }
                }
            }
            fall=!fall;

        }
    }


}

我无法继续进行，因为它变得越来越复杂，我认为有一些简单的解决方案。

Answer 1

拓扑排序以获得图表详细信息先决条件，然后从起始节点开始 dfs，以获得所需的学期数

我怎样才能解决这个关于毕业的算法难题

How can i solve this the puzzle of algorithm regarding graduation

java

algorithm

graph-algorithm