Условие задачи
Дано общее количество курсов numCourses, пронумерованных от 0 до numCourses-1.
Некоторые курсы имеют зависимости(то есть необходимо пройти другой курс перед тем как взять текущий): [0,1]
Можно ли по заданным зависимостям завершить все курсы?
пример 1
1
2
3
4
|
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
|
пример 2
1
2
3
4
5
|
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.
|
пример 3
1
2
3
4
|
4
[[2,0],[1,0],[3,1],[3,2],[1,3]]
Output: false
|
Constraints
- Гарантируется, что дублирующих ребер не будет
- 1 <=
numCourses <= 10^5
Решение
Поиск циклов
Конвертируем пары зависимостей ( ребра графа ) в список вершина – соседи, для этого заводим мапу m , ключом которой будет номер вершины, а значение – массив соседей.
Идем по каждому элементу мапы выше и проверяем на наличие циклов, для этого запускаем поиск в глубину с запоминаем пройденных вершин. Если мы пришли в вершину, а она уже была посещена – значит найден цикл и необходимо вернуть false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
func canFinish(numCourses int, prerequisites [][]int) bool {
m := make(map[int][]int, numCourses+1)
for idx:= range prerequisites {
if _, ok := m[prerequisites[idx][0]]; !ok {
m[prerequisites[idx][0]] = make([]int,0)
}
m[prerequisites[idx][0]] = append(m[prerequisites[idx][0]], prerequisites[idx][1])
}
for idx := range m {
if !helper(m,idx, map[int]int{}) {
return false
}
}
return true
}
func helper( m map[int][]int, idx int, v map[int]int) bool {
if _, ok := v[idx]; ok {
return false
}
v[idx] = 1
for jdx := range m[idx] {
if !helper(m, m[idx][jdx], v){
return false
}
delete(v, m[idx][jdx])
}
return true
}
|