CSAcademy Round #72: Spring Cleaning

問題概要

原文 → CS Academy

頂点からなる有向グラフがある。このグラフは各頂点から 本ずつ有向辺が出ており、自己ループがないことが保証されている。

はじめ、全ての頂点に対して駒が 個ずつ置かれている。ここから、以下のルールにしたがって駒を取り除くことができる。

• 頂点 から出る有向辺によって繋がっている頂点を とおくとき、 ともに駒がある場合、 にある駒を取り除くことができる。

できるだけ多くの駒を取り除くとき、この操作列を出力せよ。

解説

頂点 辺の有向グラフなので、いわゆるなもりグラフで、ループが必ず つあるグラフです。なので、それぞれの頂点に対して「ループに繋がっている頂点」であるか「ループ内の頂点」であるかのどちらかです。

ループ内の頂点から探索を始めると、ループに繋がっている頂点を取れない可能性があるので、ループに繋がっている頂点から優先的に探索をすればよいです。これをするには、入次数が である頂点から先に探索すれば良いです。

なお、ひとつの大きな閉路になっていて入次数が である頂点がひとつもない場合もあることなどに注意してください。

ソースコード

void solve(vector<int>& edge, vector<int>& visited, int cur) {
    visited[cur] = true;
    if(visited[ edge[cur] ]) return;
    solve(edge, visited, edge[cur]);
    printf("%lld %lld\n", cur+1, edge[cur]+1);
}

signed main() {
    int N; cin >> N;
    vector<int> to(N, -1), deg(N, 0), visited(N, 0);
    rep(i,0,N) {
        int p; cin >> p; p--;
        to[i] = p;
        deg[p]++;
    }

    deque<int> deq;
    rep(i,0,N) {
        if(deg[i] == 0) deq.push_front(i);
        else deq.push_back(i);
    }

    rep(i,0,N) {
        solve(to, visited, deq[i]);
    }
}