10000 - Longest Paths

[nymo]

You should try this input where your algo produces wrong answer.

Code: Select all

input:
====
6
1
1 2
1 5
2 3
3 4
4 5
5 6
0 0
0

I actaully solved this with dfs, but your bfs approach should work. You have to notice one thing ... when a nodes distance is updated [a longer path is found to reach this node], it should be enqued again.

[asif_rahman0]

r u consider it an undirected graph??
if yes dont do that.

just use simple adjacent matrix. ok

main code segment----------

Code: Select all

Q.push(s); 
        while(!Q.empty()){
            cur=Q.front();
            Q.pop();
            for(i=1;i<=n;i++){ 
                if(node[cur][i]&&(cost[cur]+1)>cost[i]){
					cost[i]=cost[cur]+1;
                    Q.push(i);
                }
            }
        }

hope its help

[smilitude]

Thanks a lot nymo, that testcase helped me to get ac.
I am not so experienced, still i got the lack that i cannot generate good testcases to check my code!


Thanks asif_rahman0 too... though if you look at my code -- this part

Code: Select all

  while(true) {
            scanf("%d%d",&a,&b);
            if(a==0 && b==0) break;
           node[a].edge[node[a].nedge++]=b;
        }

You can see, i considered it a directed graph, not undirected
I used adjacency list instead of adjacency matrix, cause i thought it might be a sparse graph. Even if its not a sparse graph, adjacency list should be better in consuming memory than adjacency matrix in this problem, and i just had a dist variable with each node, for the weight.

[h001122]

I solved "Longest Paths" by Topological Sort, but got TLE.

Certainly It was written the input wasn't a cyclic graph at all.

I don't think I got TLE because that.
What's wrong? Please help me.

Code: Select all

#include <cstdio>

bool adj[101][101] = {false};
// adj[i][j] : Are I and J connected? 
int indegree[101];
int d[101];
int n; // n : The number of Vertexes
int end;
int result = 0;

int main()
{
   int i, j;
   int Case = 1;
   while(true) {
      scanf("%d", &n);
      for(i = 1; i <= n; i++) {
         for(j = 1; j <= n; j++) adj[i][j] = false;
         indegree[i] = 0;
         d[i] = 0;
      }

      if(n == 0) break;

      int s; // s : starting vertex
      scanf("%d", &s);

      while(true) {
         int p, q;
         scanf("%d %d", &p, &q);

         if(p == 0 && q == 0) break;
         adj[p][q] = true;
         ++indegree[q];
      }
      
      // Starting Sort from vertex that we inputed
      for(i = 1; i <= n; i++) {
         if(!indegree[i] && i != s) {
            indegree[i] = 0x7FFFFFFF;
         }
      }

      indegree[s] = 0;

      int v = 0;
      while(v < n) { // Topological Sort
         bool ended = false;

         for(i = 1; i <= n; i++) {
            if(!indegree[i]) {
               ++v;
               for(j = 1; j <= n; j++) {
                  if(adj[j][i]) { // Get the distance of the Longest Path
                     if(d[j] + 1 > d[i]) d[i] = d[j] + 1;
                  }

                  if(adj[i][j]) {
                     --indegree[j];
                     --indegree[i];
                  }
               }
               if(d[i] > result) {
                  result = d[i];
                  end = i;
               }
            }
         }
      }

      for(j = 1; j <= n; j++) {
         if(!indegree[i]) break;
      }
      printf("Case%d: The longest path from %d", Case++, s);
      printf(" has length %d, finishing at %d.\n\n", result, end);
   }

   return 0;
}

Sorry My Code like rags.

[h001122]

Can this problem be solved by Topological Sort?
According to the cardinal principle, we can use TS on this problem.

[Rinoaheartilly]

I look at all the sample output that all users have posted, and my code passed them all. However I still got wrong answer... help please....

Code: Select all

#include<iostream>
using namespace std;
int main(){
   class AdjListNode{
      public:
         AdjListNode *next;
         int vert;
         AdjListNode(int v, AdjListNode *ne){
            vert = v;
            next = ne;
         }
   };
   int n, start, end, cnt, largest, v1, v2, front, rear, update;
   int m = 1;
   bool inside;
   AdjListNode *Queue[200];
   AdjListNode *Adj[200];
   AdjListNode *link, *chase;
   cin>>n;
   while(n!=0){
      for(int i=0; i<101; i++){
         Adj[i] = NULL;
      }
      cnt = 1;
      largest = -1;
      front = rear = -1;
      cin>>start;  //starting point
      cin>>v1>>v2;
      while(v1!=0 && v2!=0){         
         Adj[v1] = new AdjListNode(v2, Adj[v1]);
         cin>>v1>>v2;
      }
      link = Adj[start];
      while(link != NULL){
         inside = false;
         chase = link;
         while(Adj[chase->vert]!=NULL){
            inside = true;
            if(Adj[chase->vert]->next!=NULL){
               Queue[++rear] = chase; //There are more than 1 things in the list, so queue it so you can go back and chase
               Adj[chase->vert] = Adj[chase->vert]->next;
               update = cnt;  //save counter so you can go back
            }
            chase = Adj[chase->vert];
            cnt++;
            if(Adj[chase->vert]==NULL){
               if(cnt>largest){
                  largest = cnt;
                  end = chase->vert;
               }else if(cnt==largest){
                  if(chase->vert < end)
                     end = chase->vert;
               }
               if(front<rear){
                  if(front!=-1 && rear!=-1){
                     chase = Queue[++front];
                     cnt = update;
                  }
               }
            }
         }
         if(!inside){
            if(cnt>largest){
               largest = cnt;
               end = chase->vert;
            }else if(cnt==largest){
               if(chase->vert < end)
                  end = chase->vert;
            }
         }
         if(link->next!=NULL){
            cnt = 1;
            link = link->next;
         }else break; 
         
               
      }
      cout<<"Case "<<m<<": The longest path from "<<start<<" has length "<<largest<<", finishing at "<<end<<"."<<endl;
      m++;
      cin>>n;
   }


}

Here is my Input

Code: Select all

2
1
1 2
0 0
5
3
1 2
3 5
3 1
2 4
4 5
0 0
5
5
5 4
5 3
5 2
5 1
4 1
4 2
0 0
8
1
7 1
8 1
1 3
2 3
4 3
3 5
6 2
0 0
6
1
1 2
1 5
2 3
3 4
4 5
5 6
0 0
2
1
1 2
0 0
0

Here is the output for it

Code: Select all

Case 1: The longest path from 1 has length 1, finishing at 2.
Case 2: The longest path from 3 has length 4, finishing at 5.
Case 3: The longest path from 5 has length 2, finishing at 1.
Case 4: The longest path from 1 has length 2, finishing at 5.
Case 5: The longest path from 1 has length 5, finishing at 6.
Case 6: The longest path from 1 has length 1, finishing at 2.

[breno_pelosi]

I'm trying to solve it with BFS but i'm getting WA. I don't know what could be wrong because i tryed several input tests and i always got the correct answer.

Could anyone help me with more inputs or any ideas?

[Diablos]

I coded the problem "Longest Path" with DFS but it still gives me TLE, although I saw posts on the board that solved DFS with muuucccchhhh gooooood time....

anyway, here's my code::

Code: Select all

#include <iostream>
#include <string.h>
#include <list>
using namespace std;

#ifndef ONLINE_JUDGE
	#include <fstream>
	#define cin in
	ifstream in("10000.in");
#endif

#define max(a,b) (a>b)? a : b

struct Node{
	list<int> adj;
}Graph_B[100];
bool visited[100];
short wentTo[100];
short nNodes;

int LongestPath(short source)
{
	if(visited[source])
		return 0;
	visited[source] = true;
	int path = 0;
	for(list<int>::iterator iter= Graph_B[source].adj.begin();
			iter != Graph_B[source].adj.end(); iter++)
	{
		int i = (*iter);
		int next = LongestPath(i)+1;
		if(next > path) wentTo[source] = i;
		path = max(path, next);		
	}
	visited[source] = false;
	return path;
}


void main()
{
	cin >> nNodes;
	int Case = 1;
	while(nNodes != 0)
	{
		for(int i=0; i<nNodes; i++)
			Graph_B[i].adj.clear();
		memset(visited, 0, nNodes);
		memset(wentTo, 0xFF, nNodes*2);
		short Source;
		cin >> Source;
		Source--;
		int from, to;
		cin >> from >> to;
		while( from != 0 || to != 0)
		{
			Graph_B[from-1].adj.push_back( to-1 );
			cin >> from >> to;
		}
		cout << "Case " << Case++ << ": ";
		cout << "The longest path from " << Source+1 << " has length " << LongestPath(Source);
		int finish = Source;
		while( wentTo[finish] != -1 ) finish = wentTo[finish];
		cout << ", finishing at " << finish+1 << ".\n";
		cin >> nNodes;
	}
}

please help

[Diablos]

Correcte, finally got the AC,,,

Just with some memoization....

[Biks]

i solved this problem using backtrack
but i am getting WA
Can anyone give me some critical test case so i can check wheres wrong

[Giorgi]

i solved this problem using backtrack
but i am getting WA
Can anyone give me some critical test case so i can check wheres wrong

I think there are better ways to solve this problem.
backtrack will give TLE

try to solve it using BFS or Topological Sort

[sakhassan]

I am a very very fresher in graph... Can any buddy help me in the following code , pls !!!! waht mistake does i made ?? i use dfs

Code: Select all

#include<stdio.h>
#include<string.h>

#define N 110

struct g{

	int node;
	int status;
	int len;
	int num_edge;
	int edge[N];
}graph[N];

int stck[N];
int top;

void push(int n)
{
	stck[top]=n;
	top++;
}

int pop()
{
	int n;
	top--;
	n = stck[top];
	return n;
}

void dfs(int n)
{
	int i,j,k,l;
	//int count;
	//count = 0;
	push(n);
	graph[n].status = 2;

	while(top)
	{
		i = pop();
		graph[i].status = 3;
		j = graph[i].num_edge;
		for(k=0;k<j;k++)
		{
			l = graph[i].edge[k];
			//graph[l].len++;
			if(graph[i].len+1>graph[l].len)
				graph[l].len = graph[i].len+1;
			if( (graph[l].status == 1) )
			{
				push(l);
				graph[l].status = 2;
			}
		}
		
	}

//	printf("%d\n",count);
}

int main()
{

	int i;
	int node;
	int p,q;
	int n;
	int cases;

	cases=0;



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

		for(i=1;i<=n;i++)
		{
			graph[i].node=i;
			graph[i].status = 1;
			graph[i].num_edge=0;
			graph[i].len = 0;
			memset(graph[i].edge,0,sizeof(graph[i].edge));
		}
		memset(stck,0,sizeof(stck));
		top=0;

		scanf("%d",&node);


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

			i = graph[p].num_edge++;
			
			graph[p].edge[i]=q;

		}

		dfs(node);

		int max, end;
		max = 0;
		

		for(i=1;i<=n;i++)
		{
			if(max<graph[i].len)
			{
				max = graph[i].len;
				end = i;
			}
		}

		printf("Case %d: The longest path from %d has length %d, finishing at %d.\n",cases+1,node,max,end);
		printf("\n");

		cases++;

	
	}
	return 0;
}

what is the output for such case :

5
5
3 4
1 2
0 0

Thanks in advance

[sakhassan]

I am a very very fresher in graph... Can any buddy help me in the following code , pls !!!! waht mistake does i made ?? i use dfs

Code: Select all

#include<stdio.h> 
#include<string.h> 

#define N 110 

struct g{ 

   int node; 
   int status; 
   int len; 
   int num_edge; 
   int edge[N]; 
}graph[N]; 

int stck[N]; 
int top; 

void push(int n) 
{ 
   stck[top]=n; 
   top++; 
} 

int pop() 
{ 
   int n; 
   top--; 
   n = stck[top]; 
   return n; 
} 

void dfs(int n) 
{ 
   int i,j,k,l; 
   //int count; 
   //count = 0; 
   push(n); 
   graph[n].status = 2; 

   while(top) 
   { 
      i = pop(); 
      graph[i].status = 3; 
      j = graph[i].num_edge; 
      for(k=0;k<j;k++) 
      { 
         l = graph[i].edge[k]; 
         //graph[l].len++; 
         if(graph[i].len+1>graph[l].len) 
            graph[l].len = graph[i].len+1; 
         if( (graph[l].status == 1) ) 
         { 
            push(l); 
            graph[l].status = 2; 
         } 
      } 
       
   } 

//   printf("%d\n",count); 
} 

int main() 
{ 

   int i; 
   int node; 
   int p,q; 
   int n; 
   int cases; 

   cases=0; 



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

      for(i=1;i<=n;i++) 
      { 
         graph[i].node=i; 
         graph[i].status = 1; 
         graph[i].num_edge=0; 
         graph[i].len = 0; 
         memset(graph[i].edge,0,sizeof(graph[i].edge)); 
      } 
      memset(stck,0,sizeof(stck)); 
      top=0; 

      scanf("%d",&node); 


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

         i = graph[p].num_edge++; 
          
         graph[p].edge[i]=q; 

      } 

      dfs(node); 

      int max, end; 
      max = 0; 
       

      for(i=1;i<=n;i++) 
      { 
         if(max<graph[i].len) 
         { 
            max = graph[i].len; 
            end = i; 
         } 
      } 

      printf("Case %d: The longest path from %d has length %d, finishing at %d.\n",cases+1,node,max,end); 
      printf("\n"); 

      cases++; 

    
   } 
   return 0; 
} 

what is the output for such case :

5
5
3 4
1 2
0 0

[Jan]

Dont open a new thread if there is one already. Your input is not valid.

[Solaris]

Your program does not pass the following case:

5 1
1 2
2 3
3 4
1 3
4 5
0 0

About your input I dont think there is any such input in the judge data .. though the logical ans should be (0,5) but my AC code does not pass that as well ..

And I agree with Jan .. making new threads for each new problems of each user only makes the board messy, makes searching messier and helping harder ... but as you are VERY VERY FRESHER (after making 65 posts) decided to help you