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

Post Reply
nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo » Thu May 11, 2006 2:24 pm

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
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Thu May 11, 2006 10:28 pm

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

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Thanks nymo!

Post by smilitude » Fri May 12, 2006 8:19 am

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! :oops:


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 :D
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.
fahim
#include <smile.h>

User avatar
h001122
New poster
Posts: 9
Joined: Thu Feb 24, 2005 5:59 am

10000

Post by h001122 » Wed Jul 12, 2006 7:41 am

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.

User avatar
h001122
New poster
Posts: 9
Joined: Thu Feb 24, 2005 5:59 am

I got AC by Floyd Algorithm. but...

Post by h001122 » Wed Jul 12, 2006 8:33 am

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

Rinoaheartilly
New poster
Posts: 9
Joined: Thu Oct 14, 2004 6:37 am
Location: North Carolina

10000 WA!!! Help please!!!!

Post by Rinoaheartilly » Fri Sep 08, 2006 9:54 pm

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
New poster
Posts: 1
Joined: Tue Sep 26, 2006 5:13 pm
Location: Limeira

10000 WA

Post by breno_pelosi » Tue Sep 26, 2006 5:23 pm

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?
Tks,

Breno

Diablos
New poster
Posts: 5
Joined: Thu Oct 05, 2006 4:58 pm
Location: Egypt
Contact:

10000 - TLE

Post by Diablos » Thu Oct 05, 2006 5:08 pm

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
Mustafa M. Mohie,
Ain Shams University
Faculty of Computer and Information Sciences
http://doomdiablos.spaces.live.com
http://doomdiablos.blogspot.com

Diablos
New poster
Posts: 5
Joined: Thu Oct 05, 2006 4:58 pm
Location: Egypt
Contact:

Post by Diablos » Wed Oct 11, 2006 7:25 pm

Correcte, finally got the AC,,,

Just with some memoization....
Mustafa M. Mohie,
Ain Shams University
Faculty of Computer and Information Sciences
http://doomdiablos.spaces.live.com
http://doomdiablos.blogspot.com

Biks
New poster
Posts: 6
Joined: Sat Jun 03, 2006 12:55 pm
Location: Bangladesh

10000

Post by Biks » Sat Oct 21, 2006 5:06 pm

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
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

Re: test case for 10000 longest path

Post by Giorgi » Sun Oct 22, 2006 12:40 pm

Biks wrote: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
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Sat Oct 28, 2006 11:17 am

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
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

10000 longest path Wrong answer

Post by sakhassan » Mon Oct 30, 2006 5:33 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Oct 30, 2006 8:08 pm

Dont open a new thread if there is one already. Your input is not valid.
Ami ekhono shopno dekhi...
HomePage

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Mon Oct 30, 2006 8:45 pm

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 :)
Where's the "Any" key?

Post Reply

Return to “Volume 100 (10000-10099)”