539 - The Settlers of Catan

[russoue]

Can anyone tell me what is the problem with my code? I think I got it right but am getting WA.
Please I need help.
Thanks in advance


[c]#include <stdio.h>

int n, m, max;
int matrix[30][30];
int not_visited[30];
void dfsbt(int, int);

int main(void)
{
register int i, j;
int from, to;


scanf("%d %d", &n, &m);
while(n || m) {
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
matrix[j] = 0;
}
not_visited = 1;
}

for(i = 0; i < m; i++) {
scanf("%d %d", &from, &to);
matrix[from][to] = matrix[to][from] = 1;
}

max = 0;
for(i = 0; i < n; i++) {
if(not_visited) {
dfsbt(i, 0);
}
}
printf("%dn", max);
scanf("%d %d", &n, &m);
}

return 0;
}

void dfsbt(int node, int length)
{
register int i;

not_visited[node] = 0;
if(length > max)
max = length;

for(i = 0; i < n; i++) {
if(matrix[node]) {
matrix[node] = matrix[node] = 0;
dfsbt(i, length + 1);
matrix[node] = matrix[node] = 1;
}
}
}[/c]

[chang]

U forget to print '\n'....u print 'n'
another matter, i used dfs taking each node as starting node....I can't remember why i used so...if u get WA, u may modify it.....

[russoue]

Thanks for your reply.
Actually I was printing "\n" in my code but for unknown reason the '\' is not showing up here.

[obayashi]

I've modified your code a little and merged with my code, then got AC...

The problem with your code lies in the varible "not_visited".

There's no need to use this varible to mark the node visited.

The problems just has something to do with the EDGE not the NODE.

So to mark the node is not reasonable.

Just leave out it and you will certainly get AC.

Good luck.

p.s. I've learned a lot from your code. Thanks indeed.

[New(User)]

what's the idea for this problem ?

i tried to do a modified dfs starting from each node and memorize the longest distance but i get time limit exceeded..

here's my code:
[pascal]
program settlers;
var mat,A:array [0..50,0..50] of integer;
max:integer;
n:integer;
procedure DF(i,l:integer);
var j:integer;
begin
if (l > max) then max:=L;
for j:=1 to N do
if A[i,j]=1 then begin
A[i,j]:=0;
A[j,i]:=0;
df(j,l+1);
A[i,j]:=1;
A[j,i]:=1;
end;
end;
procedure Solve;
var i:integer;
begin
max:=0;
for i:=0 to N do
begin
A:=mat;
DF(i,0);
end;
writeln(output,max);
end;
procedure fA(m:integer);
var x,y,i:integer;
begin
for i:=1 to m do
begin
readln(input,x,y);
mat[x,y]:=1;
mat[y,x]:=1;
end;
Solve;
end;
procedure fB;
var m:integer;
begin
readln(input,n,m);
while not ((m=0) and (n=0)) do
begin
fA(m);
readln(input,n,m);
end;
end;
begin
fB;
end.
[/pascal]

[Experimenter]

i can't believe i got accepted using brute force. what a bullshit.

[Eduard]

Hello New(User)
You have some mistakes in your code.
AT first after reading make n:=n-1.Then clean your mat array after each test case.In procedure DF make j:=0 to n do.
And you will get AC.If you will have WA tell me.
Eduard

[yogeshgo05]

hell guys ..
can anybody tell why wa.. i know backtrackin is quite okay....
here's my code....

Code: Select all

[helloneo]

There is a thread on this problem already.. plz use old thread to post..

I think these lines are located at a wrong place..

Code: Select all

(*count)++; 
...
...
v.push_back((*count)); 
(*count)--; 

[yogeshgo05]

i have modified the code a bit i guess...
plz tell me why wa....

Code: Select all

[rio]

Try this test case. You'll know why WA.

Code: Select all

2 2
0 1
1 0
0 0

The answer should be 2.

ADD: Don't forget removing your code after AC.

[soyoja]

Additonal comment about rio's post. =)

It's an undirectional graph. threrfore, 0 -> 1 is same as 1 -> 0.
Good luck.

[yogeshgo05]

hey that's rite...

then rio means

0 1
1 0

if the ans is 2
then
are two different undirected edges.....
that means there can many edges b/w the same two nodes....
so that resulting in first bactracking b/w the nodes...

[rifayat samee_du]

Hello rio??
there is no input like
2 2
0 1
1 0

[Mukit Chowdhury]

got WA !!! please help me !!! give me some sample input !!!

Code: Select all

Deleted after accepted !!!!!!