No.244 ★1 Graph Problem
タグ : / 解いたユーザー数 844
作問者 :
nmnmnmnmnmnmnm
Problem Statement
A graph is a data structure consisting of vertices and edges.
Two vertices can be linked by connecting them with an edge.
You can move freely between vertices connected by an edge.
You are now given $N$ vertices.
In the initial state, no vertices are connected by edges.
The rules of the graph for connecting vertices with edges are as follows.
・An edge always connects two different vertices.
・There are never two or more edges between the same pair of vertices.
Given the initial number of vertices $N$,
find the minimum number of edges that must be added so that movement between all the vertices is possible.
Input
$N$
The initial number of vertices $N$ is given. $2 \le N \le 13$.
Output
Output the minimum number of edges that must be added on one line.
Print a newline at the end.
Sample
Sample 1
Input
2
Output
1
There are 2 vertices, vertex 0 and vertex 1.
It suffices to connect these 2 vertices with 1 edge.
Sample 2
Input
4
Output
3
There are vertex 0, vertex 1, vertex 2, and vertex 3.
For example, one way is to connect vertex 0 with vertex 1, vertex 1 with vertex 2, and vertex 2 with vertex 3.
Another way is to connect vertex 0 with vertex 1, vertex 1 with vertex 2, and vertex 1 with vertex 3.
In either case, the number of edges needed is 3.
Sample 3
Input
13
Output
12
There are 13 vertices.
There are many possible graphs that can be formed by connecting edges,
but the minimum number of edges needed is 12.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。