Posted:

**Sat Nov 19, 2005 11:31 am**I am new to C++ so i don't know bfs as well, can you kindly tell me what it is? thanks.ayon wrote:did i write bf? i think it's bfs(breadth first search), not bf(boyfriend).

Page **2** of **3**

Posted: **Sat Nov 19, 2005 11:31 am**

I am new to C++ so i don't know bfs as well, can you kindly tell me what it is? thanks.ayon wrote:did i write bf? i think it's bfs(breadth first search), not bf(boyfriend).

Posted: **Sat Nov 19, 2005 7:22 pm**

bfs is a graph algorithm. You better see your algorithm book for bfs. it is too large to describe in the forum. You cannot understand without proper figure. the procedure and description takes at least 4-5 pages with enough figures. once you learn bfs, many problems(graphs) will be very easy to solve very quickly.

best regards

best regards

Posted: **Sat Nov 19, 2005 7:46 pm**

Yap, bfs does the trick, but i am confused .... whats the prob with my code? I got WA

here is my c code :

#include<stdio.h>

unsigned long P[1010];

unsigned long a[1005][1005];

void setP(unsigned long n)

{

unsigned long i;

P[0]=0;

for(i=1;i<n;i++)

{

P*=2000;*

}

return;

}

void refresh(unsigned long p)

{

unsigned long i,j;

for(i=0;i<p;i++)

{

for(j=0;j<p;j++)

{

a*[j]=0;*

}

}

return;

}

void sort(unsigned long p)

{

unsigned long i,j,temp;

for(i=0;i<p;i++)

{

for(j=i+1;j<p;j++)

{

if(P*>P[j])*

{

temp=P*;*

P*=P[j];*

P[j]=temp;

}

}

}

return;

}

void calculate(unsigned long p)

{

unsigned long i,j;

for(i=0;i<p;i++)

{

for(j=0;j<p;j++)

{

if(a*[j] && (P**+1)<P[j])*

{

P[j]=P*+1;*

}

}

sort(p);

}

return;

}

unsigned long main(void)

{

unsigned long test,tc;

unsigned long p,d;

unsigned long i;

unsigned long r,c;

scanf("%lu",&test);

for(tc=0;tc<test;tc++)

{

scanf("%lu%d",&p,&d);

refresh(p);

setP(p);

for(i=0;i<d;i++)

{

scanf("%lu%d",&r,&c);

a[r][c]=1;

a[c][r]=1;

}

calculate(p);

for(i=1;i<p;i++)

{

printf("%lu\n",P*);*

}

printf("\n");

}

return 0;

}

here is my c code :

#include<stdio.h>

unsigned long P[1010];

unsigned long a[1005][1005];

void setP(unsigned long n)

{

unsigned long i;

P[0]=0;

for(i=1;i<n;i++)

{

P

}

return;

}

void refresh(unsigned long p)

{

unsigned long i,j;

for(i=0;i<p;i++)

{

for(j=0;j<p;j++)

{

a

}

}

return;

}

void sort(unsigned long p)

{

unsigned long i,j,temp;

for(i=0;i<p;i++)

{

for(j=i+1;j<p;j++)

{

if(P

{

temp=P

P

P[j]=temp;

}

}

}

return;

}

void calculate(unsigned long p)

{

unsigned long i,j;

for(i=0;i<p;i++)

{

for(j=0;j<p;j++)

{

if(a

{

P[j]=P

}

}

sort(p);

}

return;

}

unsigned long main(void)

{

unsigned long test,tc;

unsigned long p,d;

unsigned long i;

unsigned long r,c;

scanf("%lu",&test);

for(tc=0;tc<test;tc++)

{

scanf("%lu%d",&p,&d);

refresh(p);

setP(p);

for(i=0;i<d;i++)

{

scanf("%lu%d",&r,&c);

a[r][c]=1;

a[c][r]=1;

}

calculate(p);

for(i=1;i<p;i++)

{

printf("%lu\n",P

}

printf("\n");

}

return 0;

}

Posted: **Sat Nov 19, 2005 7:50 pm**

Well , u may use internet to know abou bfs, its not a tough one....the book of Cormen is also coolSoarer wrote:I am new to C++ so i don't know bfs as well, can you kindly tell me what it is? thanks.ayon wrote:did i write bf? i think it's bfs(breadth first search), not bf(boyfriend).

Posted: **Sat Nov 19, 2005 8:09 pm**

hey my code does print right those two outputs , still WAmisof wrote:The order of the dances doesn't matter. Even if 2 danced with 1 before 1 danced with Don Guilianni, the D. G. number of 2 is still 2.Wei-Ming Chen wrote:Oh~ That line is check code. I will delete when I submit it.

And why the outputs are 1 & 2

I thought it was 1 & (can't wrote it)

Code: Select all

```
#include<stdio.h>
unsigned long P[1010];
unsigned long a[1005][1005];
void setP(unsigned long n)
{
unsigned long i;
P[0]=0;
for(i=1;i<n;i++)
{
P[i]=2000;
}
return;
}
void refresh(unsigned long p)
{
unsigned long i,j;
for(i=0;i<p;i++)
{
for(j=0;j<p;j++)
{
a[i][j]=0;
}
}
return;
}
void sort(unsigned long p)
{
unsigned long i,j,temp;
for(i=0;i<p;i++)
{
for(j=i+1;j<p;j++)
{
if(P[i]>P[j])
{
temp=P[i];
P[i]=P[j];
P[j]=temp;
}
}
}
return;
}
void calculate(unsigned long p)
{
unsigned long i,j;
for(i=0;i<p;i++)
{
for(j=0;j<p;j++)
{
if(a[i][j] && (P[i]+1)<P[j])
{
P[j]=P[i]+1;
}
}
sort(p);
}
return;
}
unsigned long main(void)
{
unsigned long test,tc;
unsigned long p,d;
unsigned long i;
unsigned long r,c;
scanf("%lu",&test);
for(tc=0;tc<test;tc++)
{
scanf("%lu%d",&p,&d);
refresh(p);
setP(p);
for(i=0;i<d;i++)
{
scanf("%lu%d",&r,&c);
a[r][c]=1;
a[c][r]=1;
}
calculate(p);
for(i=1;i<p;i++)
{
printf("%lu\n",P[i]);
}
printf("\n");
}
return 0;
}
```

Posted: **Sat Nov 19, 2005 8:13 pm**

implemention often makes trouble when that can be solved with known algo. try the following input
your program gives
but it should be
better try with bfs, that will make your life easier...

Code: Select all

```
4 4
1 2
1 3
0 2
0 3
```

Code: Select all

```
1
1
2
```

Code: Select all

```
2
1
1
```

Posted: **Wed Dec 07, 2005 4:47 pm**

here is my code

i use bfs.But i donno where is my wrong.Give me sm i/o.

Code: Select all

```
code removed after AC....... :)
```

Posted: **Wed Dec 07, 2005 6:23 pm**

I totally overlooked the line D<=p(p-1)/2.But i think they should give me RE in stead of WA.

Posted: **Sat Apr 01, 2006 6:34 am**

I too used BFS.

It's still giving WA.

Can u tell me what u did to solve ur problem?[/code]

It's still giving WA.

Can u tell me what u did to solve ur problem?[/code]

Posted: **Sat Apr 01, 2006 6:40 am**

I too used BFS.

but it is giving WA.

Can smbd help me?

Here is the code-

but it is giving WA.

Can smbd help me?

Here is the code-

Code: Select all

```
#include<stdio.h>
int main(){
int dance[1000][1000],i,j,p,d,t,k,a,b,don[1000],c[1000];
scanf("%d",&t);
don[0]=0;
for(i=0;i<t;i++){
scanf("%d%d",&d,&p);
for(j=0;j<d;j++)
for(k=0;k<d;k++)
dance[j][k]=-1;
for(j=0;j<d;j++)
don[j]=c[j]=-1;
for(j=0;j<p;j++){
scanf("%d%d",&a,&b);
dance[a][b]=dance[b][a]=1;
}
j=0,p=1;
don[0]=0;
c[0]=0;
while(j!=d){
for(k=0;k<d;k++){
if(dance[j][k]==1 && c[k]==-1){
don[p]=k;
p++;
c[k]=c[j]+1;
}
}
j++;
}
for(j=1;j<d;j++)
printf("%d\n",c[j]);
printf("\n");
}
return 0;
}
```

Posted: **Sat Apr 01, 2006 9:35 am**

For this question, i used BFS.

But it's giving WA.

Can smbd help me?

Here is the code :

But it's giving WA.

Can smbd help me?

Here is the code :

Code: Select all

```
#include<stdio.h>
int main(){
int dance[1000][1000],i,j,p,d,t,k,a,b,don[1000],c[1000];
scanf("%d",&t);
don[0]=0;
for(i=0;i<t;i++){
scanf("%d%d",&d,&p);
for(j=0;j<d;j++)
for(k=0;k<d;k++)
dance[j][k]=-1;
for(j=0;j<d;j++)
don[j]=c[j]=-1;
for(j=0;j<p;j++){
scanf("%d%d",&a,&b);
dance[a][b]=dance[b][a]=1;
}
j=0,p=1;
don[0]=0;
c[0]=0;
while(j!=d){
for(k=0;k<d;k++){
if(dance[j][k]==1 && c[k]==-1){
don[p]=k;
p++;
c[k]=c[j]+1;
}
}
j++;
}
for(j=1;j<d;j++)
printf("%d\n",c[j]);
printf("\n");
}
return 0;
}
```

Posted: **Sun May 07, 2006 6:19 pm**

sorry for late reply.

my bfs approach......

psudocode

here is the bfs-code part....

my bfs approach......

psudocode

Code: Select all

```
for(k=0 to inf){
for(i=0 to num_of_guests_of_(k-1)th_step){
for(j=0 to D(num_of_dancing_couple) ){
if(guest_1 of j_th couple alredy marked){
check if guest_2 alredy marked or not;
}
else if(guest_2 of j_th couple alredy marked){
check if guest_1 alredy marked or not;
}
}
}
}
```

Code: Select all

```
st[0][0]=0;
t[0]=1;
for(k=0;;k++){
t[(k+1)%2]=0;
for(i=0;i<t[k%2];i++){
for(j=0;j<d;j++){
if(d1[j]==st[k%2][i]){
if(mark[d2[j]]>=mark[d1[j]]+1){
mark[d2[j]]=mark[d1[j]]+1;
st[(k+1)%2][t[(k+1)%2]++]=d2[j];
}
}
else if(d2[j]==st[k%2][i]){
if(mark[d1[j]]>=mark[d2[j]]+1){
mark[d1[j]]=mark[d2[j]]+1;
st[(k+1)%2][t[(k+1)%2]++]=d1[j];
}
}
}
}
if(t[(k+1)%2]==0)break;
}
```

Posted: **Sat Aug 12, 2006 9:54 pm**

Your code isn't working forAnkur Jaiswal wrote:For this question, i used BFS.

But it's giving WA.

Can smbd help me?

Here is the code :

Code: Select all

```
1
5 5
0 1
1 2
2 3
3 4
0 4
```

Code: Select all

```
1
2
2
1
```

Posted: **Tue Jul 17, 2007 12:05 am**

Hello, I cant find the error of this code, but I get WA.

Thank you.

Code: Select all

```
AC
```

Posted: **Tue Jul 17, 2007 4:38 pm**

Can anyone help me to find the wrong? My code is right for all inputs for this problem...