読者です 読者をやめる 読者になる 読者になる

迷いませんか?

プログラミング、電子工作、ゲーム・・・etc、色々やるけど中途半端なブログです。

最悪の記者

プログラミング 競技プログラミング C/C++

JOI本選にでることになったので非公式難易度表を埋めてるのですが、難易度7以降は考察してもなかなか解けなくてつらいです
最悪の記者解いたし、トポロジカルソート詳しく知らなかったのでせっかくだしブログ書きます。

最悪の記者

僕の考察:めんどくさい系っぽい→適当なアレでソートすればいけるのでは?→勝ちから負けに有向辺繋げばワンチャン→やっぱソートか→>無理<

解法:トポロジカルソート!!!!!!

なんか惜しいところまでいってた感あって悔しいですが、よく知らなかったので学びですね。
問題としてはトポロジカルソートして、解の一意性があるか判定すればいいっぽい。
判定は、1位→2位、2位→3位、...、n−1位→n位に辺が通ってれば解は一つらしいのでそれで判定
ソート部分はDFSがわかりやすかったのでDFSで書きました。
ヴィジュアライズされてるサイトが合ってそれで理解が深まった
「topological sort」をGoogleで検索したら出てくるけど色々なのがヴィジュアライズされてて良さそう

vector<int> G[5005];
vector<int> standings;
bool used[5005] = {};
int kind = 0;

void visit(int v){
    if(used[v]) return;
    used[v] = 1;
    int cnt = 0;
    REP(i, G[v].size()){
        visit(G[v][i]);
        cnt++;
    }
    if(cnt > 1)
        kind++;
    standings.push_back(v);
}

int main(void){
    int n, m;
    cin >> n >> m;
    REP(i, m){
        int a,b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
    }
    REP(i, n){
        visit(i);
    }
    reverse(all(standings));
    REP(i, n){
        cout << standings[i]+1 << endl;
    }
    REP(i, n-1){
        bool there = true;
        REP(j, G[standings[i]].size()){
            if(G[standings[i]][j] == standings[i+1])
                there = false;
        }
        if(there){
            cout << 1 << endl;
            return 0;
        }
    }
    cout << 0 << endl;
}