10000 - Longest Paths

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10000 - Longest Path

Post by mf » Wed Dec 24, 2008 3:07 pm

ashish_thakur wrote:Thanks , Now I am getting TL error
If you want to hear my opinion on your new TL code, you have to post it again. Or edit your previous post and update the code there.
is there any standard algo for this type of problem
One linear-time algorithm is to topologically sort the graph and then do usual dynamic programming on it. This can be implemented very compactly with DFS, in pseudocode:

Code: Select all

dfs(x):  // does depth-first search, and returns length of longest path starting at x
    if x was previously visited:
        return the previously recorded return value of dfs(x).

    res = 0;
    for every edge x->y, do:
        res = max(res, 1 + dfs(y));

    mark vertex x as visited, and record res in some array as return value of dfs(x)
    return res
Another algorithm that would work here, given the very low constraints (n<=100), and is very easy to implement is Floyd-Warshall algorithm. Normally, it is used to find shortest paths, to find the longest paths in DAGs just change the 'min' function in it to 'max'. (or, equivalently, negate the edge costs)

ashish_thakur
New poster
Posts: 7
Joined: Mon Dec 22, 2008 3:00 pm

Re: 10000 - Longest Path

Post by ashish_thakur » Wed Dec 24, 2008 6:11 pm

here is the code with TL error

Code: Select all

#include<stdio.h>
#include<stdlib.h>



struct node{
int value;
struct node * next;
};

int numNodes;
int largestDepth;

VISIT(struct node  **Node, int n){

     static int depth=0;
     struct node *NODE = Node[n];

      while(NODE!=0){
           ++depth;
          VISIT(Node,NODE->value);
          NODE=NODE->next;
      }

     if(depth>largestDepth)
          largestDepth=depth;
          depth=0;
}

int main(void){

int caseNo=1;
while(1){
int startNode;
scanf("%d",&numNodes);

     if(numNodes<1)break;
    scanf("%d",&startNode);
    struct node *Node[numNodes+1];
    int i;

for(i=1;i<numNodes+1;i++){
     Node[i]=0;
 }
int p,q;

while(1){
   scanf("%d",&p);
   scanf("%d",&q);
   if(p==0 && q==0)
         break;

   if(Node[p]==0){
         Node[p] = (struct node *)malloc(sizeof (struct node));
         Node[p]->value=q;
         Node[p]->next=0;
   }else{
       struct node * head=Node[p];
       while(head->next!=0){
       head=head->next;
   } 
 
 struct node * new= (struct node *)malloc(sizeof (struct node));
 new->value=q;
 new->next=head;
 head->next=new;
 new->next=0;
 } 
 }

VISIT(Node,startNode);
printf("Case %d: The longest path from %d has length %d finishing at %d.\n",caseNo,startNode, largestDepth,2);
largestDepth=0;
caseNo++;
}
}


mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10000 - Longest Path

Post by mf » Wed Dec 24, 2008 6:27 pm

Just implement one of the algorithms already mentioned in this thread.

What you do - brute-forcing all possible paths - is not fast enough, simply because there can be too many such paths. For example, in the worst possible input case when n=100 and the graph has n(n-1)/2 edges, there are about 10^30 paths - an astronomic number!

ashish_thakur
New poster
Posts: 7
Joined: Mon Dec 22, 2008 3:00 pm

Re: 10000 - Longest Path

Post by ashish_thakur » Sat Dec 27, 2008 8:45 pm

Hello I tried but I am geting RE with the modified changes please help me out

Code: Select all

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
   
   struct node{
    int value;
    struct node * next;
    };

    int numNodes;
    int largestDepth;
     
 
   void VISIT(struct node  **Node, int n,int *visit,int *f){ 
          
    struct node *NODE = Node[n];
    if(visit[n-1]==1)        // if visited return
        return;
    visit[n-1]=1;
    static int  depth;
    depth=0; 

          while(NODE!=0){
              if(visit[NODE->value-1]==1)
                  f[n-1]= f[n-1]>1+f[NODE->value-1]?f[n-1]:1+f[NODE->value-1];
              else 
                  VISIT(Node,NODE->value,visit,f);
              NODE=NODE->next;
              f[n-1]=f[n-1]>=depth?f[n-1]:depth; 
          }
                
         if(f[n-1]>=depth)
            depth=f[n-1]+1;
         else{
            f[n-1]=depth;
            depth+=1;
         }       
              
   }           
 
    int main(void){

    int caseNo=1;
    while(1){
    int startNode;
    scanf("%d",&numNodes);

        if(numNodes<1)break;
        
        scanf("%d",&startNode);
        struct node *Node[numNodes+1];      // to store all the nodes from 1 to numNodes           
        int i;
    int VISITED[numNodes];                     // to store visited info
    int f[numNodes];                                // to store final longest distance from each node
    memset(f,0,sizeof(int)*numNodes);
    memset(VISITED,0,sizeof(int)*numNodes);

    for(i=1;i<numNodes+1;i++){
         Node[i]=0;
    }
    int p,q;

    while(1){                                        // creating adjacency list of all the nodes
       scanf("%d",&p);
       scanf("%d",&q);
       if(p==0 && q==0)
             break;

       if(Node[p]==0){
             Node[p] = (struct node *)malloc(sizeof (struct node));
             Node[p]->value=q;
             Node[p]->next=0;
       }else{
           struct node * head=Node[p];
           while(head->next!=0){
           head=head->next;
       }

    struct node * new= (struct node *)malloc(sizeof (struct node));
    new->value=q;
    new->next=head;
    head->next=new;
    new->next=0;
    }
    }

    VISIT(Node,startNode,VISITED,f);
    printf("Case %d: The longest path from %d has length %d finishing at %d. \n",caseNo,startNode,f[startNode-1],2);
    
    caseNo++;
   

    }
    }



ashish_thakur
New poster
Posts: 7
Joined: Mon Dec 22, 2008 3:00 pm

Re: 10000 - Longest Path

Post by ashish_thakur » Sun Dec 28, 2008 10:24 am

Ok I got it return 0 was missing in main

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 10000 - Longest Path

Post by vahid sanei » Sun Mar 29, 2009 8:56 am

Code: Select all

REMOVED 
Just I change table[101][101] to table[103][103] and got Acc 
Impossible says I`m possible

Skt
New poster
Posts: 5
Joined: Wed Oct 29, 2008 2:55 pm

Re: 10000 - Longest Path

Post by Skt » Sun Oct 11, 2009 9:10 pm

#include<iostream>
#include<queue>
using namespace std;
int dist[103],maxi;
bool G[103][103];
void bfs(int node);
int main()
{
bool one = 0;
int j,i,r,c,p,q,source,pos,ans,kase = 1;
while(cin>>maxi && maxi)
{
for(i=0;i<maxi;i++) for(j = 0;j<maxi;j++) G[j] = 0;
for(i=0;i<maxi;i++) dist = 0;
cin>>source;
while(cin>>p>>q && (p||q))
G[p-1][q-1] = 1;
bfs(source-1);
ans = 0;
for(i=0;i<maxi;i++)
if(dist>ans) {pos = i+1;ans = dist;}
if(one == 1)cout<<endl<<endl;
one = 1;
cout<<"Case "<<kase++<<": The longest path from "<<source<<" has length "<<ans<<", finishing at "<<pos<<".\n";
}
return 0;
}

void bfs(int node)
{
int i,start;
queue<int> q;q.push(node);
while(!q.empty())
{
start = q.front();q.pop();
for(i=0;i<maxi;i++)
{
if(G[start] == 1 )
{
q.push(i);
dist = dist>dist[start] + 1 ? dist : dist[start]+1;
}
}
}
}

why am i getin TLE ????

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 10000 - Longest Path

Post by arifcsecu » Wed Oct 14, 2009 8:00 pm

Since vertex is 100

SO you can use Floyd warshall algorithm

hope it helps
Try to catch fish rather than asking for some fishes.

amishera
New poster
Posts: 38
Joined: Sat Dec 27, 2008 10:42 pm

Re: 10000 - Longest Path

Post by amishera » Wed Dec 23, 2009 12:41 am

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.

@mjad
New poster
Posts: 44
Joined: Thu Jul 22, 2010 9:42 am

Re: 10000 - why runtime error ?

Post by @mjad » Fri Aug 06, 2010 8:03 am

anybody help me why runtime error?
i think this is right.
please help me

Code: Select all

#include<iostream>

using namespace std;

void compare(int a[100][2],int idx,int n);
int t=-1,ix=-1;
int main()
{
int node,start,n1,n2,i,j,search[100][2],index[100],ks=0;
//freopen("10000input.txt","r",stdin);

while(1)
{
i=0;j=0;
cin>>node;
if(node==0)
break;
cin>>start;
while(1)
{
cin>>n1>>n2;
if(n1==0||n2==0)
break;
if(start==n1)
index[j++]=i;
search[i][0]=n1;
search[i][1]=n2;
i++;

}

while(j)
{
j--;
compare(search,index[j],i);
}
cout<<"Case "<<++ks<<": The longest path from "<<start<<" has length "<<t<<", finishing at "<<ix<<"."<<endl<<endl;
t=-1;ix=-1;
}

return 0;
}

void compare(int a[100][2],int idx,int n)
{
int i=0,c=1;
for(;i<n;i++)
{
if(a[i][0]==a[idx][1])
{
c++;
idx=i;
i=0;
}
}
if(c>t||((c==t)&&(ix>a[idx][1])))
{
t=c;
ix=a[idx][1];
}

}

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 10000 - Longest Path

Post by arifcsecu » Wed Sep 01, 2010 12:23 am

please
increase your array size
for 100 to 101 or more ..

hints: Why did you not use Floyd Warshall Algorithm ? it has an easy solution with simple floyd warshall algorithmm
Try to catch fish rather than asking for some fishes.

littleibex
New poster
Posts: 1
Joined: Sat Dec 17, 2011 7:50 pm

Re: 10000 - Longest Path

Post by littleibex » Sat Dec 17, 2011 7:54 pm

Hi..I am getting TLE...can anybody help me out please..here is my code

Code: Select all

#include <iostream>
#include <sstream>

using namespace std;

int max1, max2, pl;
bool map[110][110];

void go(int s, int n)
{
    for(int j = 1; j <= n; j ++)
    {
        if(map[s][j])
        {
            max2 ++;
            go(j, n);
        }
    }
    if(max2 > max1 || (max1 == max2 && s < pl))
    {
        max1 = max2;
        pl = s;
    }
    max2 --;
}

int main()
{
    int n, s, paths, a, b;
    stringstream ss;
    for(int x = 1; true; x ++)
    {
        cin >> n;
        if(n == 0)
        {
            break;
        }
        cin >> s;
        paths = 0;
        ss.str("");
        for( ; true; )
        {
            cin >> a >> b;
            if(a == 0 && b == 0)
            {
                break;
            }
            paths ++;
            ss << a << " " << b << endl;
        }
        int p[paths], q[paths];
        for(int i = 0; i < paths; i ++)
        {
            ss >> p[i] >> q[i];
        }
        for(int i = 0; i <= n; i ++)
        {
            for(int j = 0; j <= n; j ++)
            {
                map[i][j] = false;
            }
        }
        for(int i = 0; i < paths; i ++)
        {
            map[p[i]][q[i]] = true;
        }
        pl = n + 1;
        max1 = 0;
        max2 = 0;
        go(s, n);
        cout << "Case " << x << ": The longest path from " << s << " has length " << max1 << ", finishing at " << pl << ".\n\n";
    }
    return 0;
}
Thanks in advance

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10000 - Longest Path

Post by brianfry713 » Tue Jan 10, 2012 1:14 am

littleibex try using the Floyd Warshall algorithm.
Check input and AC output for thousands of problems on uDebug!

SyFy
New poster
Posts: 13
Joined: Tue Jun 19, 2012 12:16 pm
Location: Russia, Vladimir
Contact:

Re: 10000 - Longest Path

Post by SyFy » Sun Jul 01, 2012 5:14 pm

got ac with FW ... but before that got 4 WAs 'cause I forgot to print \n\n after each line of output.
it should be something like this: out.printf("Case 1: The longest path from 1 has length 2, finishing at 4.\n\n");

good luck! :D

gtg_bansal
New poster
Posts: 1
Joined: Thu Aug 02, 2012 7:45 am

Re: 10000 - Longest Path

Post by gtg_bansal » Thu Aug 02, 2012 7:54 am

Getting TLE .
This is my first submission on UVA and I am getting TLE. I am using BFS and assuming directed tree.
Please help

Code: Select all

#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
int main()
{
    int nodes,cases=0;
    scanf("%d", &nodes);
    while(nodes!=0){
        cases++;
        int start;
        scanf("%d", &start);
	int a[102][102],meta[102];
        //memset(a,0,(nodes+1)*(nodes+1)*sizeof(int));
        memset(meta,0,(nodes+1)*sizeof(int));
 //     vector< vector<int> > a(102,vector<int>(0,0));
        int p, qq;
        scanf("%d%d", &p,&qq);
        while(p!=0){
            a[p][meta[p]++]=qq;
            scanf("%d%d", &p,&qq);
        }
        queue<int> q;
        int dist[102],max,index;
        max=index=0;
        memset(dist,0,(nodes+1)*sizeof(int));
        q.push(start);
        while(!q.empty()){
            int n = q.front();
            q.pop();
            for(int i=0;i<meta[n];i++){
                int jj=a[n][i];
                q.push(jj);
                dist[jj]=dist[n]+1;
                if(index>jj && dist[jj]==max)
                    index=jj;
                if(dist[jj]>max){
                    max=dist[jj];
                    index = jj;
                }
            }
        }
        printf("Case %d: The longest path from %d has length %d, finishing at %d.\n", cases,start,max,index);
        scanf("%d", &nodes);
    }
    return 0;
}

Post Reply

Return to “Volume 100 (10000-10099)”