위상 정렬

문제 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 방향 비순환 그래프, 위상 정렬, 우선순위 큐 방향 비순환 그래프, 위상 정렬, 우선순위 큐를 합친 문제이다. 기본적인 풀이 방법은 다음과 같다. B문제를 풀기 위해서는 A문제를 먼저 풀어야 한다. 입력으로 A, B가 들어오면 A의 outdegree로 B가 추가되고, B의 indegree가 1 증가한다. 문제는 쉬운 문제부터 풀어야 하므로, 우선순위 큐로 현재 풀 수 있는 문제 중에서 난이도가 가장 낮은 문제가 top에 ..

문제 풀이 방향 비순환 그래프와 위상 정렬 알고리즘을 사용한다. B를 거치기 위해서는 무조건 A가 먼저 거쳐야 한다. B의 indegree가 증가하고, A의 outdegree가 B로 저장된다. indegree가 0인 학생부터 queue에 넣는다. queue에서 나온 학생의 outdegree에 해당하는 학생의 indegree를 1차감한다. indegree가 0이 되면 queue에 넣는다. 코드 #include #include using namespace std; int indegree[32001]; vector outdegree[32001]; vector path; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int N..

문제 풀이 방향 비순환 그래프와 위상 정렬을 이용한다. indegree가 0인 노드부터 큐에 넣는다. 큐가 empty될 때까지 검사하며 하나씩 pop한다. 검사되는 노드인 current노드와 연결된 노드인 next의 indegree를 1감소 시킨다. next노드의 indegree가 0이 되었다면 큐에 넣는다. next노드까지 소모되는 시간은 (current노드 까지 소모 시간 + next노드의 build 시간)의 최대값이다. 코드 #include #include #include #include using namespace std; int N, K, W; int build_time[1001]; int indegree[1001]; vector outdegree[1001]; vector priority[100..