導入

まず用語について軽く説明を置いておきます

DFS：深さ優先探索
トポロジカル順序：以下の図のように有向グラフ上の頂点を、全ての辺が左から右に向くように一列に並べた順序
入次数(いりじすう)：その頂点に入ってくる辺の数

alt text → alt text

想定される問題

講義Aを履修するには講義Bを履修する必要がある。このような前提条件がN個与えられてた時に全ての講義を受講できるか？

これは

各講義を頂点とした有向グラフに閉路がないか？

と言い換えられます。
このような有向グラフ上の閉路検出について、DFSとカーン法の二種類の手法で解いていきます。

両者共に時間計算量はO(V+E)O(V+E)。

Nが大きくなるとスタックオーバーフローが怖いのでカーン法を使用するのがいいと思います。
具体的にはN≤105N\leq{10^{5}}くらいならDFS、超えたらカーン法のような感じです(雰囲気で話してます)。私はDFS派

DFS

DFSについての詳しい解説は省きますが、各頂点を{ 見た / 見てない }の2パターンで管理していたところを3パターンに変えることで閉路を検出できます。
私は普段DFSでbool型のseenという変数を使うのですが、閉路検出の際はint型のstateとしています。

vector<int> state;
// state[0]: 未探索
// state[1]: 今のDFS内で訪問した
// state[2]: 確定済み

DFS内で遷移先の頂点のstateが1なら閉路があるということになります。

実装例

vector<int> state;
bool judge = false;
void dfs(map<int,vector<int>> &mp,int v){
  if(judge) return;
  state[v] = 1;
  for(auto next_v:mp[v]){
    if(state[next_v]==1){
      judge = true;
      return;
    }
    if(state[next_v]==2) continue;
    dfs(mp,next_v);
  }
  state[v]=2;
}

int main(){
  int n,m;
  cin>>n>>m;
  int u,v;
  map<int,vector<int>> mp;
  for(int i=0;i<m;i++){
    cin>>u>>v;
    u--;
    v--;
    mp[u].push_back(v);
  }
  state.assign(n,0);
  for(int i=0;i<n;i++){
    if(state[i]==0) dfs(mp,i); //未探索ならDFSする
    if(judge){
      cout<<"閉路が検出されました"<<endl;
      return 0;
    }
  }
  cout<<"閉路は検出されませんでした"<<endl;
  return 0;
}

カーン法

ざっくり概要

各頂点の入次数を管理して入次数が0の頂点から順に削除をしていきます。
削除した頂点と辺で繋がっている頂点の入次数を-1します。
これを繰り返すことで最終的に全ての頂点の入次数が0となれば閉路がないとわかります。

解説

まず標準入力を受け付けて隣接リストを作ります。
gが隣接リスト、indegが各頂点の入次数をあらわします。

int n,m;
cin>>n>>m;
vector<vector<int>> g(n);
vector<int> indeg(n,0);
int u,v;
for(int i=0;i<m;i++){
  cin>>u>>v;
  u--;
  v--;
  g[u].push_back(v);
  indeg[v]++;
}

現時点で入次数が0の頂点をqueueに入れます。

queue<int> q;
for(int i=0;i<n;i++) if(indeg[i]==0) q.push(i);

閉路の検出のためにsetを使用します。
これは普通にvectorでいいです。私がsetとタイプするのが好きなので使うことが多いです。
setを使用するとV回のループでinsertにO(log⁡N)O(\log{N})かかるので、時間計算量もO(Vlog⁡V+E)O(V\log{V}+E)に悪化します。

set<int> st;
while(!q.empty()){
  int v=q.front();
  q.pop();
  st.insert(v);
  for(auto tmp:g[v]){
    indeg[tmp]--;
    if(indeg[tmp]==0) q.push(tmp);
  }
}
if(st.size()!=n) cout<<"閉路があります"<<endl;
else cout<<"閉路はありません"<<endl;

まとめ

int n,m;
cin>>n>>m;
vector<vector<int>> g(n);
vector<int> indeg(n,0);
int u,v;
for(int i=0;i<m;i++){
  cin>>u>>v;
  u--;
  v--;
  g[u].push_back(v);
  indeg[v]++;
}
queue<int> q;
for(int i=0;i<n;i++) if(indeg[i]==0) q.push(i);
set<int> st;
while(!q.empty()){
  int v=q.front();
  q.pop();
  st.insert(v);
  for(auto tmp:g[v]){
    indeg[tmp]--;
    if(indeg[tmp]==0) q.push(tmp);
  }
}
if(st.size()!=n) cout<<"閉路があります"<<endl;
else cout<<"閉路はありません"<<endl;

最後に

これから学ぶぞという人にはカーン法の方が簡単で実装も楽かなと思います。
でもBFS / DFSってグラフ系やろうと思ったら最初くらいに学びがちだと思うのでDFSでもいけるのかな。

発展問題としては、有向グラフ上の最長経路とか経路数数え上げとかかな。
私のDP力は灰~茶レベルくらいなのでできません。