10959 - The Party, Part I

[Wei-Ming Chen]

I wrote 10959 and got WA.....
Can someone give me some I/O?
thanks...

[polone]

Code: Select all

3 3
0 1
1 2
0 2

Code: Select all

1
1

[Soarer]

Hi, I got WA too, can anyone give some more complicated inputs? Thanks.

[Wei-Ming Chen]

Can you give me more output?
My code run this output is right

[polone]

Maybe you can post your code

[Wei-Ming Chen]

#include <stdio.h>
int main()
{
return 0;
}

[misof]

First, this line: printf("%d %d %d %d %d %d\n",a[1],a[2],a[3],a[4],a[5],a[6]);
is at least strange and clearly doesn't belong into the final version of your code.

Second, the algorithm is wrong.
Consider the following input:

Code: Select all

1

3 2
1 2
0 1

Here the correct output is

Code: Select all

1
2

[Wei-Ming Chen]

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)

[misof]

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.

[Wei-Ming Chen]

I thought you are right.
I changed my code and got AC
Thank you

[Soarer]

Can anyone check it for me? Thanks.

#include<iostream>
#include<math.h>
using namespace std;

int main(){
int num_of_cases, loop = 1;
cin >> num_of_cases;
while(loop <= num_of_cases){

int num_of_people;
long num_of_dance, loop_2 = 1;
cin >> num_of_people >> num_of_dance;

int danced[num_of_people][num_of_people], number[num_of_people];

//initialization
for(int n = 0; n < num_of_people; n++){
number[n] = num_of_people;
}
number[0] = 0;

while(loop_2 <= num_of_dance){
int part_1, part_2;
cin >> part_1 >> part_2;

danced[part_1][part_2] = 1;
danced[part_2][part_1] = 1;

loop_2 ++ ;
}
for(int j = 0; j < num_of_people; j++){
for(int k = 0; k < num_of_people; k++){
if(number[k] == j){
for(int m = 0; m < num_of_people; m++){
if(number[m] > j && danced[k][m] == 1){
number[m] = j+1;
}
}
}
}
}

for(int k = 1; k < num_of_people; k++){
cout << number[k] << endl;
}

loop ++ ;
}
return 0;
}

[ayon]

believe it or not, this problem is nothing but bfs; better use bfs, that will make your life easier...

[Soarer]

believe it or not, this problem is nothing but bfs; better use bfs, that will make your life easier...

What is bf?

[Observer]

What is bf?

I guess it's not "bf", but "bfs" (Breadth First Search).

[ayon]

did i write bf? i think it's bfs(breadth first search), not bf(boyfriend).