perogram

トポロジカルソート

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B

AC Code

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3784044#1

関数化した。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;
            return empty_vector;
        }
    }
    // 正常の戻り値
    return ret;
}

別の問題