Ordering Tasks

[Boss321]

Hi, I need implementation this task. It's a graph problem but I don't know how to do it.
Anyone know how to do it? Please, I need your help.
If anyone of you did I would be very grateful!!

John has n tasks to do. Unfortunately, the tasks are not independent and the execution of one task is only possible if other tasks have already been executed.

The input will consist of several instances of the problem. Each instance begins with a line containing two integers, 1 <= n <= 100 and m. n is the number of tasks (numbered from 1 to n) and m is the number of direct precedence relations between tasks. After this, there will be m lines with two integers i and j, representing the fact that task i must be executed before task j. An instance with n = m = 0 will finish the input.

Output
For each instance, print a line with n integers representing the tasks in a possible order of execution.
Sample Input

5 4

1 2

2 3

1 3

1 5

0 0

Sample Output

1 4 2 5 3

[nuzzle]

This problem is usually called topological sorting. What differs from an ordinary sort is that the ordering is partial. Let's say you were to sort the numbers between 1 to 5. Without thinking about it you would assume there's this ordering between the elements,

1 < 2 < 3 < 4 < 5

But in this case the ordering is just partial. You have this,

1 < 2
2 < 3
1 < 3
1 < 5

One possible order is the one you suggest,

1 4 2 5 3

but note that the 4 really can appear anywhere so many orders are valid. On the other hand there may be no valid order at all. Say you added this to the above for example,

2 < 1

Here's a link,

http://en.wikipedia.org/wiki/Topological_sorting

[Boss321]

Yes, I know it. But I don't know how to implementation it. I would if I needed someone implementation it?? I am a biggener and I don't know how to do it. Very please about your help.

[nuzzle]

Yes, I know it. But I don't know how to implementation it. I would if I needed someone implementation it?? I am a biggener and I don't know how to do it. Very please about your help.

If it's a job assignment I suggest you have a little chat with your boss and explain that you're in over your head here. Or maybe you could ask a more senior collegue.

If you're a student I suggest you team up with a class mate. Everything is so much easier when you have someone to discuss and work together with. Or maybe you just don't have the prerequisities for the course you're attending. You're supposed to be able to handle an exercise at this level of difficulty aren't you? Otherwise it hadn't been given to you. In any case it's meaningless for someone else to do your homework. It's part of your learning process. You better start trying hard or you'll stay beginner forever.