Page **1** of **2**

### 539 - The Settlers of Catan

Posted: **Sun Apr 07, 2002 11:33 am**

by **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]

### >>>>>>>>>>>>

Posted: **Tue Apr 09, 2002 10:50 pm**

by **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.....

Posted: **Wed Apr 10, 2002 7:29 pm**

by **russoue**

Thanks for your reply.

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

### Solution

Posted: **Mon Aug 05, 2002 3:30 pm**

by **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.

### 539 what's the idea?

Posted: **Sat Jan 31, 2004 11:59 am**

by **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]

Posted: **Wed Feb 02, 2005 8:14 pm**

by **Experimenter**

Posted: **Tue Feb 08, 2005 1:24 pm**

by **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

### 539 why wa ..plz help

Posted: **Tue Feb 06, 2007 6:22 am**

by **yogeshgo05**

hell guys ..

can anybody tell why wa.. i know backtrackin is quite okay....

here's my code....

Posted: **Tue Feb 06, 2007 8:19 am**

by **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)--;
```

Posted: **Fri Feb 09, 2007 10:17 pm**

by **yogeshgo05**

i have modified the code a bit i guess...

plz tell me why wa....

Posted: **Sat Feb 10, 2007 7:30 pm**

by **rio**

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

The answer should be 2.

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

Posted: **Tue Feb 13, 2007 7:51 am**

by **soyoja**

Additonal comment about rio's post. =)

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

Good luck.

Posted: **Tue Feb 13, 2007 5:24 pm**

by **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...

### Re: 539 why wa ..plz help

Posted: **Tue Mar 31, 2009 12:46 pm**

by **rifayat samee_du**

Hello rio??

there is no input like

2 2

0 1

1 0

### Re: 539 why wa ..plz help

Posted: **Fri Oct 19, 2012 3:27 pm**

by **Mukit Chowdhury**

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