POJ 1236 - Network of Schools
Problem : Two questions. A) The minimum edge to add from virtual source to original graph, to make virtual source can go to all the vertices. B) The minimum edge to add on original graph, to make the whole graph become strongly connected.
Solution : Merge graph based on strongly connected set, then,
	A) The number of vertices with no in degree.
	B) If new graph has only one vertice, answer is 0. Otherwise, the answer is bigger one that the number of vertices with no in degree and the number of vertices with no out degree.
Proof :
	1. Obviously, in original graph, the vertices in the same strongly connected set can goto each other.
	2. After merging graph, the new graph G' is a DAG.
	3. The vertices with non-zero in-degree can be reached start from at least one vertice which has no in-degree.
	4. The vertices with no in-degree cannot be reached by any other vertice.
	5. The vertices with non-zero out-degree can reach at least one vertice which has no out-degree.
	6. The vertices with no out-degree cannot reach any other vertice.
	7. There is a pair set (s, t) with [max(no. of no in-degree, no. of no out-degree)] elements. The union of all paths start from si and end to ti covers the whole graph. (by 3 & 5).

	A. with 4, the answer should at least number of vertices with no in-degree. with 3, the answer should at most number of vertices with no in-degree.
	B. With 4&6, the answer should at least the bigger one of no in-degree and no out-degree. With 7, the answer should at most this number.
[]