Well, I thought a lot about how to help Spidey, even peeked at the hint ( which, sadly, din’t really help muchðŸ˜¦ )

The problem : https://dodoincfedora.wordpress.com/2009/02/19/programming-skills/

*My solution :*

*If you want the .c file,( it’ll be properly indented etc. ) I’ve put it up here : http://ankursinha.fedorapeople.org/misc/problem1.c*

/*

* My algo :

* The node with maximum number of links to the other nodes should be the result.

* In case all nodes have same number of links, Ill calculate the middle node.

* Although I dont think the above case will ever occur, I’m coding with its possibility.

* I’ll give it more thought later.

*

*/

#include

#include#define MAX_NODES 1000

#define MAX_CASES 10000

int main(int argc, char *argv[]){

int graph[MAX_NODES][MAX_NODES];

int number_cases;

int number_nodes[MAX_CASES];

int i, j,k;

int t1,t2;

int node_link_count[MAX_NODES];

int max;

/* char temp; */

if(argc > 1){

fprintf(stderr,”Error : %s No arguments may be passed to this program\n”,argv[0]);

exit (EXIT_FAILURE);

}

printf(“Enter the input cases: “);

scanf(“%d”,&number_cases);

for(i = 0 ; i < number_cases; i++){

for(k = 0; k < MAX_NODES; k++)

for(j = 0; j < MAX_NODES; j++)

graph[k][j] = 0;

for(k = 0; k < MAX_NODES; k++)

node_link_count[k] = 0;

printf(“Enter number of nodes in case %d: “,i+1);

scanf(“%d”,&number_nodes[i]);

printf(“Enter :\n” );

for(j = 0; j < (number_nodes[i] – 1); j++){

scanf(“%d %d”,&t1,&t2);graph[t1][t2] = graph[t2][t1] = 1;

}

for(j = 0; j < number_nodes[i]; j++){

for(k = 0; k < number_nodes[i]; k++){

if(graph[j][k] == 1)

node_link_count[j]++;

}

}

max = node_link_count[0];

for(j = 1; j < number_nodes[i]; j++)

if(max < node_link_count[j])

max = node_link_count[j];

if(max == node_link_count[0] && node_link_count[0] == node_link_count[1]){

printf(“Result(s) : %d”,(number_nodes[i]/2));

}

else {

printf(“Result(s) : “);

for (j = 0; j < number_nodes[i]; j++)

if (node_link_count[j] == max)

printf(“%d “,j);

printf(“\n”);

}

}

exit(EXIT_SUCCESS);

}

It does give the result as per the trial input and output, but I’m still not completely convinced that this is a fool proof method.

### Like this:

Like Loading...

*Related*

That is 90% there but “He wants to minimize the maximum distance of any house from his house”.

What you have is something to maximise the number of houses he can reach in one hop.

What he wants is to make sure the furthest away house to be not too far away so to move to the centre of the city.

I think it is just coincidence that the maximally connected nodes are in the centre in the examples.

Although I may be wrong, anyone else want to comment?

I know..That’s the reason why I said I’m not too convinced.. Any one else got a better, more apt solution ?

Just passing by.Btw, your website have great content!