# 「POJ 1236」Network of Schools

## Network of Schools

poj1236

### 输入格式

The first line contains an integer N: the number of schools in the network (2 <= N <= 100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.

### 输出格式

Your program should write two lines to the standard output. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.

### 分析

#### 题目理解

1. 至少要选几个顶点，才能做到从这些顶点出发，可以到达全部顶点。
2. 至少要加多少条边，才能使得从任何一个顶点出发，都能到达全部顶点。

#### 思路

1. 求出所有强连通分量。
2. 每个强连通分量缩成一点，则形成一个有向无环图DAG。
3. DAG上面有多少个入度为0的顶点，问题1的答案就是多少。
4. 在DAG上要加几条边，才能使得DAG变成强连通的，问题2的答案就是多少。

#### 方法

1. 若 $m \leq n$，则加了这 $n$ 条边后，已经没有入度 $0$ 点，则问题解决，一共加了 $n$ 条边。
2. 若 $m > n$，则还有 $m - n$ 个入度 $0$ 点，则从这些点以外任取一点，和这些点都连上边，即可，这还需加 $m - n$ 条边。