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.