# Algorithm

1) Input the node data S of size n

2) Input arc data(n_{i}, n_{j}), which is pairs of integers.

3) Lock for a node k without predecessors, output k and mark it. Remove all arcs containning k.

4) Continue step 3) until all node is output, or until there is no unmarked node without predecessors.

# Data Structure

## Adjacency matrix

Arcs: (1, 0) (2, 4) (1, 3) (3, 2)

0 | 1 | 2 | 3 | 4 | |

0 | 0 | 0 | 0 | 0 | 0 |

1 | 1 | 0 | 0 | 1 | 0 |

2 | 0 | 0 | 0 | 0 | 1 |

3 | 0 | 0 | 1 | 0 | 0 |

4 | 0 | 0 | 0 | 0 | 0 |

1) Find out a column n with all 0. -> column 1

2) Output node n, and remove its arcs. Arcs can be found by checking row n. -> row 1: 1 0 0 1 0 -> remove (1, 0) (1, 3)

3) continue 1) until all node is output or there is no unmarked node without predecessors (with all 0)

Result: 1 -> 0 -> 2 -> 3 -> 4

# Characteristics

1) Output result: get up -> shower -> kids up -> get dressed -> eat -> depart. Rule: left node can go to right node, but right node can not go to left node.

2) If there is a loop, then topological sorting can not output all nodes, because we can't find a node without predecessor.

3) If there is no loop, maximum number of pairs/arcs will be *n take 2*, because (3, 7) and (7, 3) cannot occur at the same time.

# Reference

http://www.mathsisfun.com/combinatorics/combinations-permutations.html — Combination & Permutation