Нужна помощь, чтобы найти наименьшее количество семестров

Question

Моя домашняя задача представляет некоторые курсы, и сколько из них зависят друг от друга.Например, первый тест (курсы, зависящие от): (1,3) (2,3) (4,1) (4,2), и мы определяем, что существует 5 курсов и 4 зависят друг от друга (Thatsпочему 5 отсутствует в списке, его просто 0)

Я знаю из топологического поиска, что следующее является правильным решением: 1 3 2 4 0

Затем мне нужно распечататьколичество семестров, необходимое для прохождения этих курсов, и я знаю, что это 3 семестра, из-за отношений между ними.Сначала мы должны пройти курс 1 и 2, чтобы пройти 3, и, поскольку у нас уже есть 1 2, мы можем пройти курс 4.

Так что мне нужна помощь в выяснении некоторого кода, который делает это.Вот где вы мне нужны, ребята, помогите

Я пытался просто посчитать курсы, которые связаны, но не удалось.Я пытался придумать что-то, что я могу сделать, но буквально ничего не появляется в качестве решения.

Класс графа:

public class Graph {

    int V;
    LinkedList<Integer> adjList[];

    public Graph(int vertex) {
        this.V = vertex;

        //We then define the num of vertexes in the adjlist
        adjList = new LinkedList[vertex];

        //Then create a new list for each vertex so we can create a link between the vertexes
        for (int i = 0; i < vertex; i++) {
            adjList[i] = new LinkedList<>();
        }
    }
    //Directed graph
    public void addEdge(int source, int destination) {
        //Add the edge from the source node to the destination node

        adjList[source].add(destination);
        adjList[destination].add(source);
    }

    //Method to print the graph if necessary
    public void printGraph(Graph graph) {
        for (int i = 0; i < graph.V; i++) {
            System.out.println("Adjacency list over vertex: " + i);
            System.out.print("head");

            for (Integer treeCrawler : graph.adjList[i]) {

                System.out.print("-> " + treeCrawler);
            }
            System.out.println("\n");
        }
    }

    public LinkedList<Integer>[] getAdjList() {
        return adjList;
    }
}

и класс топологической сортировки, алгоритм, который мы используем для задачи

public class TopologicalSort {

    int vertex;

    //This function helps the topological function recursively by marking the vertices and pushing them onto the stack
    public void topologicalHelper(int vertex, boolean marked[], Stack nodes, Graph graph) {

        List<Integer>[] list = graph.getAdjList();

        marked[vertex] = true;

        Iterator<Integer> iterator = list[vertex].iterator();
        while (iterator.hasNext()) {
            int temp = iterator.next();
            if (!marked[temp] && list[temp].size() != 0) {
                topologicalHelper(temp, marked, nodes, graph);
            }

        }
        nodes.add(vertex);
    }


    public TopologicalSort(Graph graph, int vertecies) {
        vertex = vertecies;
        Stack nodes = new Stack();
        boolean[] marked = new boolean[vertex];

        for (int i = 0; i < vertex; i++) {
            if (marked[i] == false) {
                topologicalHelper(i, marked, nodes, graph);
            }
        }
        while(!nodes.empty()) {
            System.out.print(nodes.pop() + " ");
        }
    }
}

Результат должен быть равен 3, но яЯ не приводил это число во всех моих идеях решения, мне нужна помощь или подсказки.

---

О, а вот консольный вывод

Adjacency list over vertex: 0
head

Adjacency list over vertex: 1
head-> 3-> 4

Adjacency list over vertex: 2
head-> 3-> 4

Adjacency list over vertex: 3
head-> 1-> 2

Adjacency list over vertex: 4
head-> 1-> 2

1 3 2 4 0 

Answer 1

Зависимость является направленным свойством, поэтому вы должны использовать ориентированный граф.После заполнения графа у вас будет отключенный граф с одним или несколькими деревьями.Узнайте, какие узлы являются корнями каждого дерева, и используйте DFS, чтобы получить максимальную глубину каждого дерева.Предполагая, что для каждого семестра нет ограничений на количество курсов, максимальная глубина всех деревьев является решением.

public class Graph {
int V;
ArrayList<Integer> adjList[];
boolean[] notRoot;
public Graph(int vertex) {
    this.V = vertex;
    adjList = new ArrayList[vertex];
    notRoot = new boolean[vertex];
    for (int i = 0; i < vertex; i++) {
        adjList[i] = new ArrayList<Integer>();
    }
}
public void addEdge(int a, int b) {
    //asuming b is dependent on a
    adjList[b].add(a);
    notRoot[a]=true;
}
int maxDepthDfs(int root){
    int depth=1;
    for(int i=0;i<adjList[root].size();i++){
        int child=adjList[root].get(i);
        depth=Math.max(maxDepthDfs(child)+1,depth);
    }
    return depth;
}
public int getSolution(){
    int ans=0;
    for(int i=0;i<V;i++){
        if(!notRoot[i])
            ans=Math.max(ans,maxDepthDfs(i));
    }
    return ans;
}
}

Топологическая сортировка - это просто DFS с добавлением узлов в стек (все дочерние узлы узла).сначала добавляются, а затем добавляется root).В алгоритме Кана сначала обнаруживаются корневые элементы (узлы без родителя) и вызывается только метод или эти узлы.

int maxDepthDfs(int root){
//since we are only calling this function for root nodes we need not check if nodes were previously visited
int depth=1;
for(int i=0;i<adjList[root].size();i++){
    int child=adjList[root].get(i);
    depth=Math.max(maxDepthDfs(child)+1,depth);
}
s.push(root);
return depth;
}
public int getSolution(){
    s=new Stack<Integer>();
    int ans=0;
    for(int i=0;i<V;i++){
        if(!notRoot[i])
            ans=Math.max(ans,maxDepthDfs(i));
    }
    //stack s contains result of topological sort;
    return ans;
}