Start cleanup on topological sorting

tcNickolas · web-flow · commit 96e516aeaf67 · 2017-06-19T21:32:15.000-07:00
diff --git a/src/graph/topological-sort.md b/src/graph/topological-sort.md
@@ -1,21 +1,21 @@
 <!--?title Topological Sorting -->
 #  Topological Sorting
 
-Given a directed graph with $n$ vertices and $m$ edges. You want to **renumber the vertices** so that every edge led from the top with a smaller number in the top with a large.
+You are given a directed graph with $n$ vertices and $m$ edges. You have to **number the vertices** so that every edge leads from the vertex with a smaller number assigned to the vertex with a larger one.
 
-In other words, you want to find a permutation of the vertices **(topological order)** corresponding to the order defined by all edges of the graph.
+In other words, you want to find a permutation of the vertices (**topological order**) which corresponds to the order defined by all edges of the graph.
 
-Topological sort can be **not only** (for example, if the graph is empty; or if there are three such vertices $a$, $b$, $c$, what $a$ is the way in $b$ and in $c$, but neither $b$ in $c$ nor out $c$ to $b$ get them).
+Topological order can be **non-unique** (for example, if the graph is empty; or if there exist three vertices $a$, $b$, $c$ for which there exist paths from $a$ to $b$ and from $a$ to $c$ but not paths from $b$ to $c$ or from $c$ to $b$).
 
-Topological sorting **may not** exist at all - if the graph contains cycles (because there is a contradiction: there is a path from one vertex to another, and Vice versa).
+Topological order may **not exist** at all if the graph contains cycles (because there is a contradiction: there is a path from $a$ to $b$ and vice versa).
 
-A **common problem** for topological sorting next: There are $n$ variables whose values are unknown to us. We know only about some pairs of variables, one variable less than the other. You want to check, is not controversial whether these inequalities, and if not, to give the variables in ascending order (if the answer to any issue). It is easy to notice that this is exactly the task is about finding a topological sort of the graph of $n$ vertices.
+A common problem in which topological sorting occurs is the following. There are $n$ variables with unknown values. For some variables we know that one of them is less than the other. You have to check whether these constraints are contradictory, and if not, output the variables in ascending order (if several answers are possible, output any of them). It is easy to notice that this is exactly the problem of finding topological order of a graph with $n$ vertices.
 
 ## The Algorithm
 
-For the solution we will use a depth-first-search.
+To solve this problem we will use [depth-first search](./graph/depth-first-search.html).
 
-Assume that the graph is acyclic, i.e. there is a solution. What makes the depth? When you run out of some of the peaks $v$ he tries to run along all edges emanating from $v$. Along those edges, the ends of which have already been previously visited, it doesn't pass, and along the rest goes and causes themselves from their ends.
+Let's assume that the graph is acyclic, i.e. there is a solution. What does the depth-first search do? When you run out of some of the peaks $v$ he tries to run along all edges emanating from $v$. Along those edges, the ends of which have already been previously visited, it doesn't pass, and along the rest goes and causes themselves from their ends.
 
 Thus, by the time of the call, ${\rm dfs}(v)$ all vertices that are reachable from $v$ either directly (one edge), and indirectly (by the way) - all such vertices already visited. Therefore, if we at the time of exit from ${\rm dfs}(v)$ add our peak in the beginning of a list, in the end, this list will get a **topological sort**.
 
@@ -25,16 +25,16 @@ These explanations can also be presented in a somewhat different light, through
 
 Here is an implementation, assuming that the graph is acyclic, i.e. the desired topological sort exists. If necessary, check the graph on acyclicity easy to insert into the depth, as described in the article on depth.
 
-`C++` implementation <span class="toggle-code">Show/Hide</span>
+C++ implementation <span class="toggle-code">Show/Hide</span>
 
 ```cpp
 int n; // number of vertices
 vector<int> g[MAXN]; // count
 bool used[MAXN];
 vector<int> ans;
- 
+
 void dfs (int v) {
- used[v] = true;
+  used[v] = true;
     for (size_t i=0; i<g[v].size(); ++i) {
 	    int to = g[v][i];
 	    if (!used[to])
@@ -60,8 +60,6 @@ The main function of the solution is $topological\\_sort$, it initializes markin
 
 ## Practice Problems
 
-The task list in which you want to search topological sorting:
-
 - [SPOJ TOPOSORT "Topological Sorting" [difficulty: easy]](http://www.spoj.com/problems/TOPOSORT/)
 - [UVA #10305 "Ordering Tasks" [difficulty: easy]](https://z5h64q92x9.net/proxy_u/ru-en.en/uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1246)
 - [UVA #124 "Following Orders" [difficulty: easy]](https://z5h64q92x9.net/proxy_u/ru-en.en/uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=60)
