NIKKEI Programming Contest 2019 D - Restore the Tree

D - Restore the Tree

概要

頂点の有向根付き木がある。
この木に本の辺を追加する。ただし追加する辺をとすると、はの祖先でなければならない。
追加された辺を含む全ての辺が与えられたとき、各頂点について元の根付き木における親を出力せよ。

制約

方針

根は特定できる。（根に向かう辺は追加できないため、入次数が0の頂点が根となる）

根から各頂点を探索するとき、追加された辺を使うことはショートカットになる。
（追加された辺は祖先と子孫を直接つなぐイメージ）
そのため、根から最長距離となるような辺を残せばよい。この木における親を出力する。

実装としては、深さ優先探索を行う。注意点は以下の通り。

• その頂点への最長距離が更新されたときに親の情報を更新する
• ある頂点の子の探索を始める際は、その頂点の親の探索が終わっている必要がある

（終わっていないと子の探索中に自分の最長距離が更新されてしまう可能性がある）

感想

下記を参考にしました。
poporix.hatenablog.com

解答

Submission #4119074 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
vector<vector<int>> chi; // 各頂点の子のリスト
vector<int> nPar; // 各頂点の親の数
vector<int> dist; // 根から頂点iへの距離
vector<int> ans; // 各頂点の親
 
void dfs(int x){
	// 葉なら終わり
	if(chi[x].size() == 0) return;
 
	// 子の探索
	int nChi = chi[x].size();
	rep(i, nChi){
		int nxt = chi[x][i];
 
		// 距離が更新される = より長い経路の発見 = 今までの親は親じゃない
		if(dist[nxt] < dist[x] + 1){
			dist[nxt] = dist[x] + 1;
			ans[nxt] = x;
		}
 
		// 全ての親頂点の探索が終わったら自分の子を探索する
		// そうでないと、子の探索が終わった後、自分のdistが更新される可能性がある
		nPar[nxt]--;
		if(nPar[nxt] == 0) dfs(nxt);
	}
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N, M;
	cin >> N >> M;
 
	chi = vector<vector<int>>(N+1, vector<int>());
	nPar = vector<int>(N+1, 0);
 
	rep(i, N+M-1){
		int a, b;
		cin >> a >> b;
		chi[a].push_back(b);
		nPar[b]++;
	}
 
	// 根を求める
	// 子でない頂点を探す
	vector<bool> rootCand(N+1, true);
	for(int i = 1; i <= N; i++){
		int nChi = chi[i].size();
		rep(j, nChi) rootCand[chi[i][j]] = false;
	}
 
	int root;
	for(int i = 1; i <= N; i++){
		if(rootCand[i]) root = i;
	}
 
	dist = vector<int>(N+1, 0);
	ans = vector<int>(N+1, 0);
 
	dfs(root);
 
	for(int i = 1; i <= N; i++) cout << ans[i] << endl;
}