OJ Board

Posted: **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)

Posted: **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++;
}
}

Posted: **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!

Posted: **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++;
   

    }
    }

Posted: **Sun Dec 28, 2008 10:24 am**

Ok I got it return 0 was missing in main

Posted: **Sun Mar 29, 2009 8:56 am**

Code: Select all

REMOVED 
Just I change table[101][101] to table[103][103] and got Acc

Posted: **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 ????

Posted: **Wed Oct 14, 2009 8:00 pm**

Since vertex is 100

SO you can use Floyd warshall algorithm

hope it helps

Posted: **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.

Posted: **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];
}

}

Posted: **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

Posted: **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

Posted: **Tue Jan 10, 2012 1:14 am**

littleibex try using the Floyd Warshall algorithm.

Posted: **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!

Posted: **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;
}

OJ Board

10000 - Longest Paths

Re: 10000 - Longest Path

Re: 10000 - Longest Path

Re: 10000 - Longest Path

Re: 10000 - Longest Path

Re: 10000 - Longest Path

Re: 10000 - Longest Path

Re: 10000 - Longest Path

Re: 10000 - Longest Path

Re: 10000 - Longest Path

Re: 10000 - why runtime error ?

Re: 10000 - Longest Path

Re: 10000 - Longest Path

Re: 10000 - Longest Path

Re: 10000 - Longest Path

Re: 10000 - Longest Path