yukicoder : No.277 根掘り葉掘り

最初想定誤解法やらかしてしまい気分はギアッチョ。
http://yukicoder.me/problems/666

問題

根付き木を成すグラフが与えられる。
各頂点について、最寄の葉または根からの最短距離を求めよ。

解法

自分はDFS2回で解いた。

1回目では、各頂点でsubtree内の最寄の葉からの距離を求める。
この段階では親側に最寄の葉または根があるケースに対処できない。
よって2回目のDFSでは、各頂点が((親から最寄の葉または根までの距離)+1)の方が最短距離になるケースを処理していく。

ダイクストラ法の要領で、親及び根から最短距離を求めていく手法でもいいようだ。

int N;
vector<int> E[101010];
int dist[1010];

int dfs1(int cur,int pre) {
	
	if(cur==0 || E[cur].size()>1) {
		dist[cur]=101010;
		FORR(r,E[cur]) if(r!=pre) dist[cur]=min(dist[cur],1+dfs1(r,cur));
	}
	return dist[cur];
}

void dfs2(int cur,int pre,int par) {
	dist[cur]=min(dist[cur],par);
	FORR(r,E[cur]) if(r!=pre) dfs2(r,cur,dist[cur]+1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs1(0,-1);
	dfs2(0,-1,0);
	
	FOR(i,N) _P("%d\n",dist[i]);
}

まとめ

でも4部派です。