トポロジカルソート

ライブラリ code トポロジカルソート

関数化した。code

VI topological_sort(VV& G){
    ll N = G.size();
    
    // 入次数
    VI IN(N, 0);
    rep(i, N){
        for(ll to : G[i]){
            IN[to]++;
        }
    }

    stack<ll> st; // 入次数0のものを入れる
    rep(i, N){
        if(IN[i]==0) st.push(i);
    }

    VI ret;
    while(!st.empty()){
        ll i = st.top();
        st.pop();
        ret.push_back(i);
        for(ll to : G[i]){
            IN[to]--;
            if(IN[to]==0){
                st.push(to);
            }
        }
    }

    // 成功したか確認
    for(ll in : IN){
        if(in!=0){
            // 失敗（DAGじゃなかった）
            VI empty_vector;
            debug("not DAG");
            return empty_vector;
        }
    }
    // 正常の戻り値
    return ret;
}

トポロジカルソートを使う別の問題 (verified)

トポロジカルソートとdfs逆順の関係

  • 「全ての点から深さ優先探索を行い、その帰りがけ順がトポロジカルソートの結果になる」というのがあります
  • https://atcoder.jp/contests/dp/tasks/dp_g これはトポロジカルソートを使うように見えて、実はdfs + メモ化再帰で解ける
  • 「トポロジカルソート使いそう」と思ったときは「dfs + メモ化再帰でもいけないか？」と考えよう

木ではない帰りがけの使用例