# Topological Sorting

In some country, there are n flights among n cities. Each city has an exactly one outgoing flight but may have no incoming flight or multiple incoming flights. Design an algorithm to find the largest subset S of cities such that each city in S has at least one incoming flight from another city in S. (hint: recall the in-degree array we used in developing the topological sort algorithm in class)

I'm a little lost about how to approach this problem. The in-degree array algorithm is used to perform a Topological sort, but how does that relate to solving this problem?

HINT: First, model this as a digraph $$G$$ in the obvious way.
Next, remove all vertices of indegree 0 in $$G$$ and call the resulting graph $$G_1$$. Then remove all vertices $$v$$ of indegree 0 in $$G_1$$ and call the resulting graph $$G_2$$. Keep repeating until there are no vertices of indegree 0 to remove i.e., for general $$i$$ remove all vertices $$v$$ of indegree 0 in $$G_i$$ and call the resulting graph $$G_{i+1}$$, and stop doing this pruning when $$G_{i+1}=G_i$$.
The remaining graph is a collection of vertex-disjoint directed cycles (i.e., every vertex has both indegree and outdegree of 1) and the vertex-set of this graph is precisely the set $$S$$ that you are seeking.