Проблема может быть найдена по адресу: https://leetcode.com/problems/course-schedule/
Необходимо вернуть значение true, если в графе существует цикл, в противном случае - false.
Я пытаюсь реализовать обнаружение цикла в ориентированном графе. но это не дает правильный вывод. Логика здесь заключается в том, что всякий раз, когда я вижу вершину с неопределенностью == 0, я добавляю ее в очередь и уменьшаю степень ее соседей на 1, пока очередь не станет пустой, и поддерживаю счет вершин с неопределенностью == 0. Вконец, если число == numCourses (см. проблему по leetcode), что означает отсутствие цикла.
Один из входов, для которых я получаю неправильный вывод: numCourses = 2, prerequisites = [[0, 1]]. Может кто-нибудь сказать, пожалуйста, что я делаю не так?
if(prerequisites.length== 0) return true;
int[] indegree= new int[numCourses];
Map<Integer, List<Integer>> map= new HashMap();
for(int[] pre: prerequisites){
List<Integer> list= map.getOrDefault(pre[1], new ArrayList());
list.add(pre[0]);
indegree[pre[0]]++;
map.put(pre[1], list);
}
Queue<Integer> q= new LinkedList();
int count= 0;
for(int i= 0; i< indegree.length; i++){
if(indegree[i]== 0){
q.add(indegree[i]);
}
}
while(!q.isEmpty()){
int front= q.poll();
if(indegree[front]== 0){
count++;
}
if(!map.containsKey(front))
continue;
for(int neighbor: map.get(front)){
indegree[neighbor]--;
if(indegree[neighbor]== 0)
q.add(neighbor);
}
}
return count== numCourses;
}