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

500点です。
問題リンク

結局何を求めればいいのかの考察はすぐ終わりましたが、それをどう実装するのかでそれなりに詰まりました。

解説

　「子孫へ有向辺を引く」とあります。このことから、新しい辺を引くことによって、根からその頂点への最短距離は短くなった、ということが言えます。つまり、各頂点への最長経路で通る辺が元の木というわけです。

　これを実装します。トポロジカルソートを用いた解法がわかりやすくてよいと聞きましたが、今回は自分が採用したBFS(幅優先探索)を用いた解法を解説します。トポロジカルソートは名前しか知りませんでした。

　最長経路の探索はよくわかりませんが、最短経路ならできます。辺に重みがないのでBFSをしてやればよいですね。そこで、BFSをして、見つかった最短経路の辺を消していくことを考えます。
　頂点によっては親が複数いるわけですが、本来親は1つだけなので、この親のうち一番頂点から遠いものから伸びている辺だけ残し、残りの辺を消して仕舞えばいいです。

　BFSの実装方針です。BFSなので、根からの距離が短い経路から順にわかっていきます。根からBFSを行ってある親からある頂点に到達した時、

• その頂点の親が他にあれば、今通ってきた親を「その頂点の親リスト」から消す。BFSのqueueへのpushは行わない
• 他に親がなければ今通ってきた親は真の親である。その頂点をBFSのqueueにpushする

　「pushを行わない」という部分は重要で、これを行わなければ同じ頂点からの探索を何度も繰り返すことになり無駄が増えます。僕はこれで計算量が爆発することを全く考えずTLEを出しました。また、最長経路を見つけたいので、最後にその頂点を訪れた時だけpushします。この点でも普通のBFSとは異なります。

▶ソースコードを開く

int n, m;
std::vector<int> edge[100005];
std::set<int> parent[100005];
int ans[100005];

void bfs(int rt){
	std::queue<int> que;
	que.push(rt);
	while(!que.empty()){
		int vis = que.front();
		que.pop();
		for(int i = 0; i < edge[vis].size(); i++){
			int next = edge[vis][i];
			if(parent[next].size() > 1){
				parent[next].erase(vis);
			}else{
				ans[next] = vis;
				que.push(next);
			}
		}
	}
	return;
}

signed main(){
	scanf("%ld %ld", &n, &m);
	for(int i = 0; i < n+m-1; i++){
		int a, b;
		scanf("%ld %ld", &a, &b);
		edge[a].push_back(b);
		parent[b].insert(a);
	}
	for(int i = 1; i <= n; i++){
		if(parent[i].size() == 0){
			bfs(i);
			break;
		}
	}
	for(int i = 1; i <= n; i++){
		printf("%ld\n", ans[i]);
	}
	return 0;
}