11597 - Spanning Subtree

[yiuyuho]

I see that the answer is trivially n/2, but why is that true?

[Tausiq]

How many edges are possible if vertex_number = 4 ?
as there is no self-loop, u can draw 6 edges
try this using pen-paper

similarly, when vertex_number = 6,
highest number of edges = 15

Code: Select all

int edges = 0;
for ( int i = 1; i <= vertex_number; i++ ) {
    for ( int j = i + 1; j <= vertex_number; j++ ) {
        edges ++;
}

to form a spanning tree with 6 vertices, we must need 5 edges
its very simple, when there are n vertices
we need at least (n - 1) edges to form a spanning tree

so, Number of vertices = 6
highest number of edges = 15
minimum 5 edges needed to form a spanning tree
eventually, we can form 3 spanning trees (15 / 5)

[zobayer]

From combinatorics, it is way too easy to find the required solution. However I am interested if n is odd. Can anyone explain what will happen if n is odd? What I guess is, if n > 3, and n is odd, it is always 2. Is it ok? Find me a path to more of a mathematical proof.

[Shafaet_du]

Easy problem. in an complete graph you have n*(n-1)/2 edges and you need n-1 edges to form each spanning tree.

[AhmadKhatar]

Hi!
Does anybody know how can I reduce my runtime to zero?
Here is my code:

Code: Select all

#include <stdio.h>

int main()
{
	int n;
	int caseNo = 1;

	scanf( "%d", &n );
	while ( n != 0 )
	{
		printf( "Case %d: %d\n", caseNo++, n >> 1 );
		scanf( "%d", &n );
	}

	return 0;
}

Thanks in advance!