首先肯定是tarjan缩点。

对于第一个子任务，就是求入度为0的点数。

对于第二个子任务，数据似乎给的全都是一开始就连通的图，但是题目没给这种限制，我们这样做：
把DAG的方向消去后的连通块叫做一个“传递链”。
(1)只有一个强连通分量的时候，答案是0，这个传递链的i = 1, o = 1。
(2)不止一个强连通分量的时候，首先求出每个传递链里面的入度、出度为零的点数i、o，然后求 所有传递链 的 max(i, o) 的和，这个和就是答案。


证明如下：

对于每个传递链，首先将其变成A->B的形式。
对于仅有一个强连通分量C的传递链，需要添加0条边，因为已经成为了C->C的形式。
对于不止一个强连通分量的传递链，需要添加min(i, o) - 1条边，即可变成A->B的形式。

然后有k个传递链，每个都是Ak->Bk的形式，显然添加k条边即可将其变成一个环。也就是平均每个传递链对答案在这方面的贡献是1。

从而无论一个传递链有1或更多个强连通分量，其对答案的总贡献都是max(i, o)。


子任务1：
tarjan缩点，同一个强连通分量并入同一个并查集。
计算每个点的出入度。
输出入度为0的点的个数。

子任务2的具体步骤可以这样：
（子任务1已经做过了：求每个点的出入度）
（假设不止有1个强连通分量，并且假设已经是DAG了）
统计每个点的情况，是“软件源”点的记2，是“软件终极接收者”的点记1，什么都不是的记0，都是的记3。
消除边的方向，方法是遍历每个边，将其关联的两个点并入同一个并查集。
分别求出每个传递链上 源、终极接收者 的数量 i, o（利用前面统计的情况）。
输出Sum(max(i, o))。

• Re:似乎数据不够强但是正确算法如下 (10) 1120131805 2014-08-09 17:00:21