UVa 13038 - Directed Forest

Source

A Bangladeshi Contest at SUST(20151212)
UVa 13038

問題概要

ノード数 $N$,枝数 $M$ の有向グラフの森が与えられる.
つまり,枝を両向きに通れるとしてもサイクルができないようなグラフが与えられる.
ノードを幾つかのグループに分割するが,ノード $u$ がノード $v$ の祖先(つまりノード $u$ からノード $v$ に辿り着ける)ならば,ノード $u$ とノード $v$ は同じグループに属してはいけない.
もちろん,全てのノードはちょうど $1$ つのグループに属さなかればいけない.
グループの数の最小値を求める問題.

解法

パスに含まれるノードは全て違うグループにしなければいけないので,最も長いパスに含まれるノード数が答え.
動的計画法にて,各ノードからそのノードを始点とする最も長いパスの長さを計算していけば良い.
時間計算量は $O(N)$.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年07月25日05時38分09秒
Last modified: 2015年12月16日01時49分53秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151212_1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: