全国統一プログラミング王決定戦予選 : D - Restore the Tree

最近ほんとAtCoder奮わないな…。
https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_d

問題

祖先から子孫方向に辺が向いている、根付き木をなす有向グラフがあったとする。
ここにいくつか有向辺を追加したものを考える。
追加した辺は、元のグラフで祖先・子孫の関係にある頂点間においてのみ、祖先から子孫に向けた辺となっている。

追加後のグラフが与えられるので、元のグラフを構成せよ。

解法

トポロジカルソートを行いつつ、各頂点は親頂点群のうち最後に処理されたものを元のグラフにおける親頂点とみなせばよい。

int N,M;
set<int> E[101010];
set<int> RE[101010];
int in[101010];
int par[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N-1+M) {
		cin>>x>>y;
		E[x].insert(y);
		RE[y].insert(x);
	}
	
	FOR(i,N) if(RE[i+1].empty()) {
		E[0].insert(i+1);
		RE[i+1].insert(0);
	}
	
	queue<int> Q;
	Q.push(0);
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		FORR(e,E[x]) {
			RE[e].erase(x);
			if(RE[e].empty()) {
				par[e]=x;
				Q.push(e);
			}
		}
	}
	
	for(i=1;i<=N;i++) cout<<par[i]<<endl;
	
	
}

まとめ

ここらへんまではいいんだけどね…。