# anyone know the solution?

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 09-28-2005
heeroyung
anyone know the solution?
Emily is a teacher. She likes to give candies to her students on days near festivals. She would like to give the candies to the students in order.

She decides to distribute the candies to them one by one, with a rule that if student A is teased by B, A can receive candy before B. But this is a troublesome and time consuming task as she is very busy.

You are asked to help Emily by writing a program to find the order of students that satisfies the rule.

Input

The first line of the input file contains an integer N (2 £ N £ 100), the number of students. The students are numbered as 1 to N. The following N lines describe each student being teased by whom. In the Kth line of those N lines, the first integer M (0 £ M < N) contains the number of students who tease student K, and the next M integers are the student numbers who tease student K.

Output

The output file should contain the sequence of student numbers separated by a space that Emily can distribute the candies with the rule satisfied. If there is more than one solution, you are only required to output anyone of them. If there is no solution, output "No Solution".

Sample Input 1

5
2 2 3
1 3
1 5
1 2
0

Sample Output 1

1 4 2 3 5

Sample Input 2

5
2 2 3
1 3
1 4
1 2
0

Sample Output 2

No Solution

do anyone know how to solve this problem?
• 09-28-2005
Rashakil Fol
I assume you can figure out input and output okay.

Here's a hint for you. This problem uses a datastructure that represents a graph.
• 09-28-2005
cwr
Here's another hint for you: Read This
• 09-28-2005
Salem
> do anyone know how to solve this problem?

This is a little story about four people named Everyone, Someone, Anyone, and Noone.

There was an important job to be done and Everyone was sure that Someone would do it.

Anyone could have done it, but Noone did it.

Someone got angry about that because it was Everyone's job.

Everyone thought that Anyone could do it, but Noone realized that Everyone wouldn't do it.

It ended up that Everyone blamed Someone when Noone did what Anyone could have done
• 09-28-2005
Ancient Dragon
Quote:

Originally Posted by Salem
> do anyone know how to solve this problem?

This is a little story about four people named Everyone, Someone, Anyone, and Noone.

There was an important job to be done and Everyone was sure that Someone would do it.

Anyone could have done it, but Noone did it.

Someone got angry about that because it was Everyone's job.

Everyone thought that Anyone could do it, but Noone realized that Everyone wouldn't do it.

It ended up that Everyone blamed Someone when Noone did what Anyone could have done

:D :D :D :D I haven't heard that one before. :D :D
• 09-28-2005
heeroyung
Quote:

Originally Posted by cwr
Here's another hint for you: Read This

this is not my homework!this is a question from Hong Kong Computer Olympiad. i study this question just for my own interest.
• 09-28-2005
heeroyung
Quote:

Originally Posted by Rashakil Fol
I assume you can figure out input and output okay.

Here's a hint for you. This problem uses a datastructure that represents a graph.

do you mean using array?let me try first
• 09-28-2005
Thantos
Quote:

Originally Posted by heeroyung
this is not my homework!this is a question from Hong Kong Computer Olympiad. i study this question just for my own interest.

Then actually study it. Asking if any of us know how to solve it doesn't help you at all.
• 09-28-2005
heeroyung
Quote:

Originally Posted by Thantos
Then actually study it. Asking if any of us know how to solve it doesn't help you at all.

i have already think this problem for two days. i don't think it's wrong to ask for some hints.
• 09-29-2005
Rashakil Fol
Are you familiar with graphs?

Topological sort.
• 09-29-2005
heeroyung
Topological sort
what's the meaning of this word?
• 09-29-2005
Salem
> what's the meaning of this word?
• 09-29-2005
Thantos
Quote:

Originally Posted by heeroyung
i have already think this problem for two days. i don't think it's wrong to ask for some hints.

Then how about sharing some of the ideas that didn't work. Sorry but I don't believe you. If you show at least some attempt then we can actually aid you.
• 09-29-2005
heeroyung
Quote:

Originally Posted by Thantos
Then how about sharing some of the ideas that didn't work. Sorry but I don't believe you. If you show at least some attempt then we can actually aid you.

No need to say sorry. That's normal.

This question require us to find a correct order of students. This can be done by making an array, e.g.
Code:

`student[5]={1,2,3,4,5}`
, and then do swapping.if student 4 is teased by 1.the final array should be like that:{4,2,3,1,5}. The hardest problem is there may have some contradiction. e.g. student 4 is teased by 1 but student 1 is also teased by student 4! this come to another output--no solution. yesterday i thought one method---use array to store each student, and the following space store the number of students who tease this student. but i don't think this is a good method because the file size may be very large and the running time may be very long. so i hope to hear some opinions from you.

(if you still don't trust me, you can ask me to explain. since my english standard is very low, i hope you can understand what i am saying above.)
• 09-30-2005
heeroyung
no one help me..................
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last