Sorting Algorithm with constraints I am looking for a sorting algorithm to help me in my work. My objective is the following: after receiving an input of this kind:

5 4
1 2
2 3
3 4
4 5


The first line tells me how many ids I have, and the second number tells me how many connections. The following lines tell me the connections, and tell me that the first Id comes before the second one, for example: 1 comes before 2, 2 comes before 3, and so on. And if an impossible situation occurs:

3 2
1 2
2 3
3 1


or

2 2
1 2
2 1


I want to be able to send an error message.

Or even when there is not enough information to have a conclusive sorting:

4 4
1 2
3 1
3 4
4 2


Is there an algorithm that already does this? or can u give me some guide lines to how to start my work? The sorting part is not hard, but the impossible/insuficient info cases is what I am struggling to implement.

Thanks in advance for your time.
In other words, you are given a directed graph, and you want to know:


Whether there are any directed cycles, i.e., whether your graph is a DAG.
Assuming there are no directed cycles, whether the corresponding partial order is a linear order.


As KWillets comments, this is just topological ordering. In your case, to find whether your digraph is a DAG supporting a unique topological ordering, try the following algorithm:


Verify that there is a unique source (a node with no incoming edges).
Remove the unique source, and repeat.


This succeeds iff your digraph is a DAG which has a unique topological ordering.