#9362. 校园网络【[USACO]Network of Schools加强版】(洛谷 - P2812)

校园网络【[USACO]Network of Schools加强版】(洛谷 - P2812)

说明

共有 n 所学校 (1n10000) 已知他们实现设计好的网络共 m 条线路,为了保证高速,网络是单向的。现在请你告诉他们至少选几所学校作为共享软件的母机,能使每所学校都可以用上。再告诉他们至少要添加几条线路能使任意一所学校作为母机都可以使别的学校使用上软件。

输入格式

第一行一个正整数 n

接下来 n 行每行有若干个整数,用空格隔开。

i+1 行,每行输入若干个非零整数 x,表示从 ix 有一条线路。以 0 作为结束标志。

输出格式

第一行一个整数,表示至少选几所学校作为共享软件的母机,能使每所学校都可以用上。

第二行一个整数,表示至少要添加几条线路能使任意一所学校作为母机都可以使别的学校使用上软件。

5
2 0
4 0
5 0
1 0
0
2
2

提示

POJ 原题。数据扩大了 100 倍。

1 边数 50000001n10000

实际上,1n100001 边数 50000


原题链接

Source

图论 强连通分量