Page 7 of 11
Posted: Thu May 11, 2006 2:24 pm

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.

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

### Thanks nymo!

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

### 10000

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

Code: Select all

``````#include <cstdio>

// adj[i][j] : Are I and J connected?
int indegree;
int d;
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.

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

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

Posted: 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(){
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.
``````

### 10000 WA

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

### 10000 - TLE

Posted: 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{
}Graph_B;
bool visited;
short wentTo;
short nNodes;

int LongestPath(short source)
{
if(visited[source])
return 0;
visited[source] = true;
int path = 0;
{
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;
}
}``````

Posted: Wed Oct 11, 2006 7:25 pm
Correcte, finally got the AC,,,

Just with some memoization....

### 10000

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

### Re: test case for 10000 longest path

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

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

### 10000 longest path Wrong answer

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

Posted: Mon Oct 30, 2006 8:08 pm
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 