N 코스가 있고 1에서 N까지 레이블이 지정되어 있다고 가정합니다. 또한 관계 배열을 제공했습니다. 여기서 관계[i] =[X, Y]는 코스 X와 코스 Y 사이의 전제 관계를 나타냅니다. 따라서 이것은 의미합니다. 과정 X는 과정 Y보다 먼저 공부해야 합니다.
우리가 공부하는 과정의 모든 전제 조건을 공부했다면 한 학기에 원하는 수의 과정을 공부할 수 있습니다. 우리는 모든 과정을 공부하는 데 필요한 최소 학기 수를 찾아야 합니다. 그리고 모든 과정을 공부할 방법이 없다면 -1을 반환합니다.
따라서 입력이 N =3, 관계식 =[[1,3],[2,3]]인 경우 첫 학기에는 1과 2를 공부하므로 출력은 2가 됩니다. 2학기에는 3과목을 공부합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
코스 :=n
-
방문:=크기가 n+1인 배열이고 이를 false로 채웁니다.
-
대기열 :=새 목록
-
그래프 :=n+1 하위 목록의 목록
-
in_degree :=n+1 크기의 배열, 0으로 채움
-
관계의 각 i에 대해 수행
-
그래프 끝에 i[1] 삽입[i[0]]
-
in_degree[i[1]] :=in_degree[i[1]] + 1
-
-
학기 :=1
-
범위 1에서 n+1까지의 i에 대해 수행
-
in_degree[i]가 0이면
-
큐 끝에 i 삽입
-
방문[i] :=사실
-
-
-
학기 :=1
-
코스 :=코스 - 대기열 크기
-
대기열이 비어 있지 않고 과정이 0이 아닌 동안 수행
-
current_size :=큐의 크기
-
current_size가 0이 아닌 동안 수행
-
current_course :=대기열[0]
-
대기열에서 첫 번째 요소 삭제
-
현재 크기 :=현재 크기 - 1
-
그래프[current_course]의 각 i에 대해 수행
-
in_degree[i] :=in_degree[i] - 1
-
내가 방문하지 않고 in_degree[i]가 0이면
-
과정 :=과정 - 1
-
큐 끝에 i 삽입
-
방문[i]:=참
-
-
-
-
학기 :=학기 + 1
-
-
과정이 0이면 학기를 반환하고 그렇지 않으면 -1
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
class Solution(object): def minimumSemesters(self, n, relations): courses = n visited = [False for i in range(n+1)] queue = [] graph = [[] for i in range(n+1)] in_degree = [0 for i in range(n+1)] for i in relations: graph[i[0]].append(i[1]) in_degree[i[1]]+=1 semeseter = 1 for i in range(1,n+1): if not in_degree[i]: queue.append(i) visited[i] = True semester = 1 courses -= len(queue) while queue and courses: current_size = len(queue) while current_size: current_course = queue[0] queue.pop(0) current_size-=1 for i in graph[current_course]: in_degree[i]-=1 if not visited[i] and not in_degree[i]: courses-=1 queue.append(i) visited[i]=True semester+=1 return semester if not courses else -1 ob = Solution() print(ob.minimumSemesters(3,[[1,3],[2,3]]))
입력
3, [[1,3],[2,3]]
출력
-1