No.244 ★１のグラフの問題
nmnmnmnmnmnmnm問題文最終更新日: 2016-05-17 23:45:13
問題文
グラフとは頂点と辺からなるデータ構造のことである。
頂点と頂点の間を辺で繋ぐことで頂点と頂点を結ぶことができる。
頂点と頂点を辺で繋いだ頂点間を自由に移動できる。
いま頂点が$N$個与えられる。
最初の状態ですべての頂点は辺で繋がっていない。
頂点と頂点を辺で繋ぐときのグラフのルールは次のようなものである。
・辺は必ず異なる頂点間を繋ぐ。
・同じ頂点と頂点の間に２本以上の辺は無い。
最初からある頂点の数$N$が与えられるので、
すべての頂点を移動できるように繋ぐ必要のある最少の辺の本数を答えよ。
入力
$N$
最初からある頂点の数$N$が与えられる。$2 \le N \le 13$。
出力
繋ぐ必要のある最少の辺の数を1行で出力せよ。
最後に改行すること。
サンプル
サンプル1
入力
2
出力
1
頂点0と頂点1の2個の頂点がある。
この2つの頂点を1つの辺で繋げば良い。
サンプル2
入力
4
出力
3
頂点0と頂点1と頂点2と頂点3がある。
例えば、頂点0と頂点1、頂点1と頂点2、頂点2と頂点3を繋ぐ方法がある。
別に、頂点0と頂点1、頂点1と頂点2、頂点1と頂点3を繋ぐ方法もある。
どちらにしろ繋ぐのに必要な辺の本数は3本である。
サンプル3
入力
13
出力
12
13個の頂点がある。
辺を繋いでできるグラフのパターンはたくさんあるが、
必要な最少の辺の本数は12本である。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。