公式

D - 科目の履修順序 / Course Enrollment Order 解説 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)

投稿日時:
最終更新: