Может ли DFS выполнять топологическую сортировку на графе * И * определять, есть ли на графике цикл в одно и то же время?

Question

Я задавал вопрос по leetcode относительно расписания курсов (https://leetcode.com/problems/course-schedule/description/#=)

, но мне кажется, что я почему-то действительно запутываюсь. Я считаю, что эта проблема эквивалентна определению ее представления в виде графа.имеет топологическую сортировку. Но только ориентированные ациклические графы могут иметь топологическую сортировку - поэтому мы должны либо заранее проверить, есть ли у нее цикл, либо проверить, есть ли у него цикл, просматривая его и выполняя топологическую сортировку.

Одно из опубликованных решений, использующих DFS, выглядит следующим образом:

public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            ArrayList[] graph = new ArrayList[numCourses];
            for(int i=0;i<numCourses;i++)
                graph[i] = new ArrayList();

            boolean[] visited = new boolean[numCourses];
            for(int i=0; i<prerequisites.length;i++){
                graph[prerequisites[i][1]].add(prerequisites[i][0]);
            }

            for(int i=0; i<numCourses; i++){
                if(!dfs(graph,visited,i))
                    return false;
            }
            return true;
        }

        private boolean dfs(ArrayList[] graph, boolean[] visited, int course){
            if(visited[course])
                return false;
            else
                visited[course] = true;;

            for(int i=0; i<graph[course].size();i++){
                if(!dfs(graph,visited,(int)graph[course].get(i)))
                    return false;
            }
            visited[course] = false;
            return true;
        }
    }

Похоже, все, что он делает, проверяет, посещался ли ранее узел (курс) - но не так ливозможно, что узел был посещен ранее, но в графе не должно быть цикла? Как этот код проверяет, что цикла нет, чтобы он знал, что имеет топологическую сортировку?