Restore the Tree [全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 D]

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_d

前提知識

• トポロジカルソート

解説

https://atcoder.jp/contests/nikkei2019-qual/submissions/4101570

まず、N頂点の木があり、ある頂点uからその子孫vに辺がはられている。
これは全体で見ると、DAGになっている。
DAGに対して深さを割り当てていくには、トポロジカルソートを使おう。
根の深さを0として、遷移先に深さ+1することで深さを決定していく。
複数の遷移先によって、複数の深さを割り当てられることもあるが、
最大の深さを採用すればいい。
こうすることで、親の深さ＜子の深さを保つことができる。
この辺はよく使うテクなので、覚えておこう。
　
適切に深さを決定したあとは、どの辺を使うかの判定である。
N頂点の木について深さを決定したものを考えてみると、
使われている辺では深さの差が1になっている。
そして、追加された辺は深さの差が2以上になっている。
なので、深さの差が1である辺を採用すれば答え。

int N, M;
vector<int> E[101010];
int dep[101010];
//---------------------------------------------------------------------------------------------------
int ans[101010];
void _main() {
    cin >> N >> M;
 
    TopologicalSort ts(N);
 
    rep(i, 0, N + M - 1) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        ts.add_edge(a, b);
    }
    
    vector<int> ord;
    ts.sort(ord);
 
    fore(cu, ord) fore(to, E[cu]) chmax(dep[to], dep[cu] + 1);
 
    int root = ord[0];
    ans[root] = -1;
    rep(cu, 0, N) fore(to, E[cu]) if (dep[cu] + 1 == dep[to]) ans[to] = cu;
 
    rep(i, 0, N) printf("%d\n", ans[i] + 1);
}