Hi,
My code is getting time limit exceeded. The core logic is below:
Code: Select all
[b]path_info find_longest(int s, int visited_nodes[], linked_list* adj_list[MAX_NODES], int n)
{
// make current node s visted
visited_nodes[s] = 1;
int max = 0;
int dest = s;
// for each of its neibhors find the longest path
for (linked_list* p = adj_list[s];p != NULL;p = p->next)
{
int i = p->value;
if (visited_nodes[i] == 0)
{
path_info t = find_longest(i, visited_nodes, adj_list, n);
if (t.max+1 > max)
{
max = t.max+1;
dest = t.destination;
}
else if (t.max+1 == max)
{
dest = (dest < t.destination) ? dest : t.destination;
}
}
}
// then find the longest among the neighbors
visited_nodes[s] = 0;
path_info p;
p.max = max;
p.destination = dest;
return p;
}
[/b]
And the complete code is:
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODES 100
typedef struct _path_info
{
int max;
int destination;
} path_info;
typedef struct tag_linked_list linked_list;
struct tag_linked_list
{
int value;
linked_list* next;
};
void list_insert(linked_list** lst, int x)
{
// create a new node
linked_list* node = (linked_list*) malloc(sizeof(linked_list));
node->value = x;
node->next = *lst;
// make it the new head
*lst = node;
}
void initialize_adj_list(linked_list* adj_list[], int n)
{
for (int i = 0;i < n;i++)
{
adj_list[i] = NULL;
}
}
[b]path_info find_longest(int s, int visited_nodes[], linked_list* adj_list[MAX_NODES], int n)
{
// make current node s visted
visited_nodes[s] = 1;
int max = 0;
int dest = s;
// for each of its neibhors find the longest path
for (linked_list* p = adj_list[s];p != NULL;p = p->next)
{
int i = p->value;
if (visited_nodes[i] == 0)
{
path_info t = find_longest(i, visited_nodes, adj_list, n);
if (t.max+1 > max)
{
max = t.max+1;
dest = t.destination;
}
else if (t.max+1 == max)
{
dest = (dest < t.destination) ? dest : t.destination;
}
}
}
// then find the longest among the neighbors
visited_nodes[s] = 0;
path_info p;
p.max = max;
p.destination = dest;
return p;
}
[/b]
void free_linked_list(linked_list* lst)
{
if (lst != NULL)
{
free_linked_list(lst->next);
free(lst);
}
}
void destroy_adj_list(linked_list* adj_list[], int n)
{
for (int i = 0;i < n;i++)
{
free_linked_list(adj_list[i]);
}
}
int get_inputs(int* n, int* s, linked_list* adj_list[])
{
scanf(" %d",n);
// check exit condition
if (*n == 0)
{
return 1;
}
scanf(" %d",s);
initialize_adj_list(adj_list, *n);
int p,q;
while (1)
{
scanf(" %d %d",&p,&q);
if (p == 0 && q == 0)
{
break;
}
list_insert(&adj_list[p-1], q-1);
}
}
int main()
{
int counter = 0;
int is_first = 1;
while (1)
{
int n;
int s;
linked_list *adj_list[MAX_NODES];
// take inputs
// check exit condition
if (get_inputs(&n, &s, adj_list))
{
break;
}
// find the longest path recursively
int visited_nodes[MAX_NODES];
for (int i = 0;i < n;i++)
{
visited_nodes[i] = 0;
}
path_info path = find_longest(s-1, visited_nodes, adj_list, n);
counter++;
if (is_first)
{
is_first = 0;
}
else
{
printf("\n");
}
printf("Case %d: The longest path from %d has length %d, finishing at %d.\n",counter, s, path.max, path.destination+1);
//destroy_adj_list(adj_list, n);
}
return 0;
}
What the find_longest is doing is for a given node finding whether it has some neighbors and for each neighbor finding the longest path recursively. whenever a recursive call is made, the current node marks itself as visited by setting the array visited_nodes[s] = 1 and upon exit setting the array visited[s] = 0 so that this node can be reached via other nodes in a different path to get a different length. To prevent cycles, visited_nodes keep track of the nodes already encounted along the path (by setting visited_nodes[1]) and by checking visited_nodes
== 0 we explore a not visited node.
Is my logic correct or something is not right here?
Some help would be greatly appreciated.
Thanks.