Graph Theory - Minimization by degree problem I'm a 3rd year Math undergrad and I decided to take an algorithms extra class. This question was a bonus one on my mid-term and I still have no idea on how to approach it.

Given $n$ vertices, each labeled with a number from $[1...n]$ and $m$
  distinct pairs of those labels, you are allowed to place a directed edge between the two nodes of any such pair.
Devise an efficient procedure to determine the minimum number of nodes left with in degree equal to $0$, after an optimal choice of edges is done. Here, an optimal choice is made in such a way that as many nodes as possible have  in degree greater than $0$.
Hint : Is constructing the graph absolutely necessary ?  

Example :
$m=n=5$
and the pair set $p=\{(1,2),(2,3),(3,4),(5,2),(5,3)\}$
One possible solution :

To me, this question seems like it doesn't really have anything to do with graphs, it strikes me more as a dynamic programming trick question. Maybe there are some theorems or results that I'm not aware of that could help here.
 A: The $m$ unordered pairs you're given to begin with can be thought of as an undirected graph. Clearly the solution can be found separately for each connected component of the graph, so assume without loss of generality that we have just an $m$-edge connected graph on $n$ nodes.
Now if the graph is a tree (that is, if $m=n-1$), then there needs to be a node with in-degree $0$; there are not enough edges to point towards all of the nodes. But we'll never need to leave more than one node without in-pointing edges. Just select an arbitrary node to be the unlucky one. Since the graph is a tree, each edge can be given a well-defined direction away from the unlucky node, and this will hit every node that is not our chosen root.
If the graph is not a tree, then we can always do even better and leave no nodes with in-degree $0$. Simply select a spanning tree. By assumption that is an edge that is not part of the spanning tree; choose an arbitrary direction for that, and declare its target to be the root of the spanning tree. Then, as before, hit every non-root node with an edge away-from-the-root in the spanning tree. Finally give the edges not yet processed arbitrary directions.
What this adds up to is that the number we're being asked for is simply

The number of connected components in the original graph where the connected component contains fewer edges than nodes.

This can be computed by a simple depth- or breadth-first scan through the graph to identify connected components and count their sizes (edges and nodes) while doing so.
(Incidentally, you can easily extend this algorithm to actually produce a winning direction assignment in linear time, since a DFS or BFS implicitly constructs a spanning tree as part of its operation. But the question doesn't ask for this extension; it just wants the count).
