OJ Board

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?

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

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.

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.

Data has no cycles. BFS can revisit a node even with no cycles.
No cycles there, and BFS would do: 1 2 3 (from 1) 3 (from 2, revisited)

Saludos,
HoraPe

horape wrote: 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

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.

tlucz wrote: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

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!

Could someone check my code? Thanks!

Please help me.
I really don`t know why I got WA with this code.
Thanks a lot![/c]

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?

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

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

Examiner wrote:

Bodo wrote: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.

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]

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