标签 - Kosaraju

? 解题记录 ? ? BZOJ ? ? Kosaraju ? ? 状态压缩 ? ? 莫队 ?    2018-09-25 08:12:04    869    0    0
Description在Byteland 一共有n 座城市,编号依次为1 到n,这些城市之间通过m 条单向公路连接。对于两座不同的城市a 和 b,如果a 能通过这些单向道路直接或间接到达b,且b 也能如此到达a,那么它们就会被认为是一对友好城市。Byt eland 的交通系统十分特殊,第i 天只有编号在[li, ri] 的单向公路允许通行,请写一个程序,计算每天友好城 市的对数。 注意:(a, b) 与(b, a) 没有区别。   Input第一行包含三个正整数n, m, q,分别表示城市的个数、单向公路的条数以及询问的天数。 接下来m 行,每行两个正整数ui, vi,表示一条从城
? 解题记录 ? ? 洛谷 ? ? Kosaraju ?    2017-07-29 15:59:34    553    0    0
题目背景浙江省的几所OI强校的神犇发明了一种人工智能,可以AC任何题目,所以他们决定建立一个网络来共享这个软件。但是由于他们脑力劳动过多导致全身无力身体被♂掏♂空,他们来找你帮助他们。 题目描述共有n所学校(n<=10000)已知他们实现设计好的网络共m条线路,为了保证高速,网络是单向的。现在请你告诉他们至少选几所学校作为共享软件的母机母鸡,能使每所学校都可以用上。再告诉他们至少要添加几条线路能使任意一所学校作为母机母鸡都可以使别的学校使用上软件。 输入输出格式输入格式:   第一行一个整数n。 接下来n行每行有若干个整数,用空格空格隔开。 第i-1行的非零整数x,表示从i到x