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

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[100];
bool visited[100];
short wentTo[100];
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

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