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

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

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

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

Posted: Sat Nov 19, 2005 8:09 pm
misof wrote:
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)
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.
hey my code does print right those two outputs , still WA

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

Code: Select all

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

Code: Select all

``````1
1
2
``````
but it should be

Code: Select all

``````2
1
1
``````
better try with bfs, that will make your life easier...

### 10959 - The Party, Part I

Posted: Wed Dec 07, 2005 4:47 pm
here is my code

Code: Select all

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

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

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.

### Problem in 10959

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]

### Problem in 10959

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-

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

### 10959 - The Party, Part I

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 :

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

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;
}
}
}
}
``````
here is the bfs-code part....

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

``````

### Re: 10959 The Party Part I.... Getting WA :(

Posted: Sat Aug 12, 2006 9:54 pm
Ankur 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``````
The correct output:

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.

Code: Select all

``````AC
``````
Thank you.

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