## 10000 - Longest Paths

Moderator: Board moderators

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

### Re: 10000 - Longest Path

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

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 * new= (struct node *)malloc(sizeof (struct node));
new->value=q;
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

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

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 * new= (struct node *)malloc(sizeof (struct node));
new->value=q;
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

Ok I got it return 0 was missing in main

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

### Re: 10000 - Longest Path

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

#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

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

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
{
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;

{
int value;
};

{
// create a new node
node->value = x;
node->next = *lst;

// make it the new head
*lst = node;
}

{
for (int i = 0;i < n;i++)
{
}
}

{
// make current node s visted
visited_nodes[s] = 1;

int max = 0;
int dest = s;
// for each of its neibhors find the longest path
{
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]
{
if (lst != NULL)
{
free(lst);
}
}

{
for (int i = 0;i < n;i++)
{
}
}

{
scanf(" %d",n);

// check exit condition
if (*n == 0)
{
return 1;
}

scanf(" %d",s);

int p,q;

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

int main()
{
int counter = 0;
int is_first = 1;

while (1)
{
int n;
int s;

// take inputs
// check exit condition
{
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);
}

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.

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

### Re: 10000 - why runtime error ?

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

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

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

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;
}
``````

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

### Re: 10000 - Longest Path

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
Contact:

### Re: 10000 - Longest Path

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!

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

### Re: 10000 - Longest Path

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

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;
}
``````