Hatena::Grouptopcoder

yambe2002の日記

 | 

2016-03-29

SRM686 Div2 Easy: TreeAndVertex

21:30

2ヶ月ぶりのSRM本番。


木構造を表す配列Tree[]がある。ノードi+1はノードTree[i]とつながっている。

ノードをいずれか一つ取り除いた時、木はいくつに分けられるか。その最大数を求めよ。

ノードとつながっているエッジ数の最大値を返せば良い。

public class TreeAndVertex {
    public int get(int[] tree) {
        var conn = new int[101];

        for (int i = 0; i < tree.Length; i++)
        {
            conn[i + 1]++;
            conn[tree[i]]++;
        }

        return conn.Max();
    }
}
 |