Official
D - 科目の履修順序 / Course Enrollment Order Editorial
by
D - 科目の履修順序 / Course Enrollment Order Editorial
by
kyopro_friends
「現在履修可能な科目を列挙し、そのうち番号が最小のものを履修する」という愚直なアルゴリズムでは、1 回あたり \(\Omega(N)\) 時間かかるため、全体で \(\Omega(N^2)\) 時間かかり TLE します。
これを高速化することを考えましょう。
「現在履修可能な科目」を優先度付きキューで管理することで、その中から番号が最小のものを探し出すことは \(O(\log N)\) でできます。
この優先度付きキューの更新を考えます。科目 \(i\) を履修したことで新たに履修可能になる科目は、科目 \(i\) を前提とする科目に限ります。また、それらの科目が実際に履修可能になったかどうかは、未履修の前提科目の個数が \(0\) になったかどうかで判定できます。
よって、各科目 \(i\) について「科目 \(i\) を前提とする科目の一覧」と「科目 \(i\) の前提科目のうち未履修なものの個数」を管理・更新することにより、1 回あたり \(O(\log N)\) 、全体で \(O(N \log N)\) でこの問題を解くことができます。
実装例 (C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
// ab[i] は科目 i を前提とする科目のリスト
vector<vector<int>>ab(n);
// deg[i] は科目 i の前提科目のうち未履修なものの個数
vector<int>deg(n);
for(int i=0; i<m; i++){
int a,b;
cin >> a >> b;
a--, b--;
ab[a].push_back(b);
deg[b]++;
}
set<int>s;
for(int i=0; i<n; i++){
if(deg[i] == 0){
s.insert(i);
}
}
while(s.size()){
int i=*s.begin();
s.erase(s.begin());
cout << i+1 << ' ';
for(auto b: ab[i]){
deg[b]--;
if(deg[b] == 0){
s.insert(b);
}
}
}
}
実装例 (Python)
import heapq
N, M = map(int, input().split())
# AB[i] は科目 i を前提とする科目のリスト
AB = [[] for _ in range(N)]
# deg[i] は科目 i の前提科目のうち未履修なものの個数
deg = [0] * N
for _ in range(M):
A, B = map(int, input().split())
A -= 1
B -= 1
AB[A].append(B)
deg[B] += 1
q = []
for i in range(N):
if deg[i] == 0:
heapq.heappush(q, i)
ans = []
while len(q) > 0:
i = heapq.heappop(q)
ans.append(i+1)
for B in AB[i]:
deg[B] -= 1
if deg[B] == 0:
heapq.heappush(q, B)
print(*ans)
posted:
last update:
