## 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

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)
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
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
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

### Thanks nymo!

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

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

### 10000

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.

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

--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
New poster
Posts: 9
Joined: Thu Feb 24, 2005 5:59 am

### I got AC by Floyd Algorithm. but...

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

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(){
public:
int vert;
vert = v;
next = ne;
}
};
int n, start, end, cnt, largest, v1, v2, front, rear, update;
int m = 1;
bool inside;
cin>>n;
while(n!=0){
for(int i=0; i<101; i++){
}
cnt = 1;
largest = -1;
front = rear = -1;
cin>>start;  //starting point
cin>>v1>>v2;
while(v1!=0 && v2!=0){
cin>>v1>>v2;
}
inside = false;
inside = true;
Queue[++rear] = chase; //There are more than 1 things in the list, so queue it so you can go back and chase
update = cnt;  //save counter so you can go back
}
cnt++;
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;
}
}
cnt = 1;
}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

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

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{
}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;
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++)
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)
{
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;
}
}``````
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:
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

### 10000

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

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

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

### 10000 longest path Wrong answer

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