10000  Longest Paths
Moderator: Board moderators

 New poster
 Posts: 4
 Joined: Sun Feb 01, 2004 12:44 pm
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?
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?

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm

 New poster
 Posts: 4
 Joined: Sun Feb 01, 2004 12:44 pm
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.
[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.
Data has no cycles. BFS can revisit a node even with no cycles.Kevin Waugh wrote: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.
Code: Select all
1 > 2
1 > 3
2 > 3
Saludos,
HoraPe
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.
[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.

 New poster
 Posts: 38
 Joined: Thu Mar 27, 2003 9:12 pm
 Location: Aguascalientes, Mexico
 Contact:
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!
[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!
There are 10 kind of people on this world: those who understand binary and those who don't!

 New poster
 Posts: 3
 Joined: Tue Dec 30, 2003 6:24 pm
 Location: Brazil
 Contact:
10000
Please help me.
I really don`t know why I got WA with this code.
Thanks a lot![/c]
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[i1][j1]=1;
scanf("%d%d", &i, &j);
}
DFS(s1, 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;
}
Alexandre Tymoszenko
Topological Sorting
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?
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?
Re: Topological Sorting
If you put Dist[v] = inf, then your algorithm should be accepted.Bodo wrote:2. Dist(v) = 1 for all nodes, D(Source)=0.
What's in your hands, I think and hope, is intelligence: the ability to see the machine as more than when you were first led up to it, that you can make it more.
Alan J. Perlis
Alan J. Perlis
Re: Topological Sorting
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.Examiner wrote:If you put Dist[v] = inf, then your algorithm should be accepted.Bodo wrote:2. Dist(v) = 1 for all nodes, D(Source)=0.

 New poster
 Posts: 3
 Joined: Tue Dec 30, 2003 6:24 pm
 Location: Brazil
 Contact:
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]
[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]
Alexandre Tymoszenko
10000why wrong answer?
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);
}
}
be a good man