10000 - Longest Paths

[Kevin Waugh]

The problem statement claims that the graph has no cycles, but my BFS times out unless I check that I only visit each node once. When I do the check, my program WAs.

When I searched the forums there's a post under the Fix Forum that the dataset for this problem was increase. It seems as if this new data has cycles in it?

[little joey]

My program would shurely time out on cycles, and it doesn't, so there are no cycles.
Don't cause unnecessary panic, please.

[Kevin Waugh]

The following code wrong answers on 10000:

[cpp]
#include <cstdio>
#include <queue>
#include <utility>
#include <map>
#include <list>

using namespace std;

int main() {
int n;
int c = 1;
while (scanf(" %d", &n) == 1 && n) {
map<int, list<int> > edge;
bool visit[101] = {false};
int s;
scanf(" %d", &s);
int p, q;
while(scanf(" %d %d", &p, &q) == 2 && p && q)
edge[p].push_back(q);

queue< pair<int, int> > bfs;
bfs.push(pair<int,int>(s,0));
int md, mn;
md = 0;
mn = s;
while(!bfs.empty()) {
int cn = bfs.front().first;
int d = bfs.front().second;
bfs.pop();
visit[cn] = true;

if (d > md || (md == d && cn < mn)) {
md = d;
mn = cn;
}

for(list<int>::iterator i = edge[cn].begin();
i != edge[cn].end(); ++i)
if (!visit[*i])
bfs.push(pair<int,int>(*i, d+1));
}

printf("Case %d: The longest path from %d has length %d,"
" finishing at %d.\n\n", c++, s, md, mn);
}
}
[/cpp]


This code times out, and the only thing that is changed is that this code has no checking for revisiting nodes.
[cpp]
#include <cstdio>
#include <queue>
#include <utility>
#include <map>
#include <list>

using namespace std;

int main() {
int n;
int c = 1;
while (scanf(" %d", &n) == 1 && n) {
map<int, list<int> > edge;
int s;
scanf(" %d", &s);
int p, q;
while(scanf(" %d %d", &p, &q) == 2 && p && q)
edge[p].push_back(q);

queue< pair<int, int> > bfs;
bfs.push(pair<int,int>(s,0));
int md, mn;
md = 0;
mn = s;
while(!bfs.empty()) {
int cn = bfs.front().first;
int d = bfs.front().second;
bfs.pop();

if (d > md || (md == d && cn < mn)) {
md = d;
mn = cn;
}

for(list<int>::iterator i = edge[cn].begin();
i != edge[cn].end(); ++i)
bfs.push(pair<int,int>(*i, d+1));
}

printf("Case %d: The longest path from %d has length %d,"
" finishing at %d.\n\n", c++, s, md, mn);
}
}
[/cpp]

So either the sample data has cycles or I'm missing something obvious Didn't mean to cause a panic.

[horape]

The following code wrong answers on 10000:

...

This code times out, and the only thing that is changed is that this code has no checking for revisiting nodes.
...

[/cpp]

So either the sample data has cycles or I'm missing something obvious Didn't mean to cause a panic.

Data has no cycles. BFS can revisit a node even with no cycles.

Code: Select all

1 -> 2
1 -> 3
2 -> 3

No cycles there, and BFS would do: 1 2 3 (from 1) 3 (from 2, revisited)

Saludos,
HoraPe

[horape]

BFS can revisit a node even with no cycles.

BFS won't revisit nodes only if graph is a tree.

An undirected graph has no cycles iff it is a tree, maybe your mistake comes from that.

A directed graph can have no cycles and not be a tree.

Saludos,
HoraPe

[tlucz]

I found, why my program gave WA. That was a long line in my program:


[cpp]cout << "Case " << przypadek << ": The longest path from " << poczatek << " has length " << maks << ", finishing at " << najm[poczatek] << "." << endl << endl; [/cpp]

My mail klient wrap this line.

When I change this line on 4 lines

[cpp]cout << "Case " << przypadek << ": The longest path from " << poczatek;
cout << " has length ";
cout << maks << ", finishing at ";
cout << najm[poczatek] << "." << endl << endl;[/cpp]

I've got Accepted reply.
So, you must watch on too long lines.

[horape]

I found, why my program gave WA. That was a long line in my program:

My mail klient wrap this line.

...

So, you must watch on too long lines.

Or use other mail client. Submitting with the web form is even better.

Saludos,
HoraPe

[Pier]

Can someone check my code?

[pascal]
Var
c,f,i,l,n,p,q,t: byte;
a: array [1..100,1..100] of boolean;

Procedure visita(v: byte);
var j: byte;
begin
for j:= 1 to n do
if not a[v,j] then
begin
a[v,j]:= true;
Inc(t);
visita(j);
end;
if (t>l) or ((t=l) and (v<f)) then
begin
l:= t; f:= v;
end;
Dec(t);
end;

Begin
readln(input,n); c:= 0;
While (n<>0) do
begin
Inc(c);
fillchar (a, sizeof(a), true);
readln(input,i);
l:= 0; f:= i; t:= 0;
readln(input,p,q);
While (p<>0) and (q<>0) do
begin
a[p,q]:= false;
readln(input,p,q);
end;
visita(i);
writeln(output,'Case ',c,': The longest path from ',i,' has length ',l,', finishing at ',f,'.');
writeln(output);
readln(input,n);
end;
End.
[/pascal]

I checked it severeal times but I keep getting WA! Thanks for your time!

[Pier]

Could someone check my code? Thanks!

[tymoszenko]

Please help me.
I really don`t know why I got WA with this code.

Code: Select all

#include <stdio.h>
int g[101][101], marked[101], parent[101], leaf[101], nl;

void refreshMarks(int u, int value, int n){
   int i;
   for(i=0;i<n;i++)
     if (parent[i]==u){
       marked[i]=value;
       break;
   }
   if (i<n) refreshMarks(i, value+1, n);
}

void DFS_visit(int u, int length, int n){
   int i, sons=0;
   marked[u]=length;
   for(i=0;i<n;i++){
     if (g[u][i]&&!marked[i]){
       sons++;
       parent[i]=u;
       DFS_visit(i, length+1, n);
     }
     else if (g[u][i]&&marked[i]<length+1){
       parent[i]=u;
       sons++;
       marked[i]=length+1;
       refreshMarks(i, length+2, n);
     }
   }
   if (sons==0) leaf[nl++]=u;
}

int DFS(int s, int n){
   int i;
   nl=0;
   for(i=0;i<n;i++) marked[i]=0;
   for(i=0;i<n;i++) parent[i]=i;
   for(i=s;i<n;i++)
     if (!marked[i])
        DFS_visit(i, 1, n);
}

int calculeLengthPath(int i, int length){
   if (i==parent[i]) return length;
   else calculeLengthPath(parent[i], length+1);
}

int main(){
   int n, s, i, j, cont=1, max, longNode;
   while(1){
     scanf("%d", &n);
     if (!n) break;
     scanf("%d", &s);
     memset(g, 0, sizeof(g));
     scanf("%d%d", &i, &j);
     while(i>0&&j>0){
       g[i-1][j-1]=1;
       scanf("%d%d", &i, &j);
     }
     DFS(s-1, n);
     longNode=101;
     for(i=max=0;i<nl;i++) {
        j=calculeLengthPath(leaf[i], 0);
        if (max<=j) {
           max=j;
           if (longNode>leaf[i]) longNode=leaf[i];
        }
     }
     printf("Case %d: The longest path from %d has length %d, finishing at %d.\n\n",
         cont++, s, max, longNode+1);
   }
   return 0;
}

Thanks a lot![/c]

[Bodo]

I tried to solve the problem as follows:
1. Order the nodes topologically (we have an acyclic graph here).
2. Dist(v) = -1 for all nodes, D(Source)=0.
3. For all nodes v in that order:
- For all edges from v to x:
- if(D(v)+1>D(x))
- D(x)=D(v)+1
4. Output the node x with maximum D(x) (if there is a tie, smallest x).

Is there something wrong with my algorithm?

[Examiner]

2. Dist(v) = -1 for all nodes, D(Source)=0.

If you put Dist[v] = -inf, then your algorithm should be accepted.

[Bodo]

2. Dist(v) = -1 for all nodes, D(Source)=0.

If you put Dist[v] = -inf, then your algorithm should be accepted.

Actually, I handle -1 as -inf. The problem was not my algorithm, but the input. See the "Fixing mistakes" section for more details. Now I received "AC" with my algorithm.

[tymoszenko]

I corrected this problem and got AC. I changed DFS for BFS.

[c]void BFS(int u, int n){
int tail, head, i, t;
for(i=0;i<n;i++) marked=-1;
head=tail=0;
queue[tail++]=u;
marked=0;
while(head!=tail){
u=queue[head++];
for(i=0;i<n;i++)
if (g&&marked<marked+1){
marked=marked+1;
queue[tail++]=i;
}
}
}[/c][/c]

[joshila21]

i submitted the following code and get wrong answer.
is there any critical input or i am making a silly mistake?
please some one help me.


#include <stdio.h>

struct {
long s;
long d;
long length;
}x[11000],max;

void find_largest_distance(long,long,long);

void main (void)
{
long i,j,k,l,n,temp1,temp2,start,count=1;
while(1)
{
scanf("%ld",&n);
if(!n)break;
if(count!=1)printf("\n");
scanf("%ld",&start);
i=0;max.length=-1;
while(1)
{
scanf("%ld%ld",&temp1,&temp2);
if(!temp1 && !temp2)break;
x.s=temp1;
x.d=temp2;
x[i++].length=0;
}
find_largest_distance(start,1,i);
printf("Case %ld: The longest path from %ld has length %ld, finishing at %ld.\n",count,start,max.length,max.d);
count++;
}
}

void find_largest_distance(long vertex_,long length_,long n)
{
long i;
for(i=0;i<n;i++)
if(vertex_==x.s)
if(x.length<length_)
{
x.length=length_;
if(length_>=max.length)
{
max.length=length_;
max.d=x.d;
}
find_largest_distance(x.d,length_+1,n);
}
}