#P18168. Challenge Matrix Multiplication
Challenge Matrix Multiplication
Challenge Matrix Multiplication
对于一个有向无环图,计算每个顶点能够到达的顶点数通常不容易。Little tarjen 声称自己有一种几乎线性的算法,并生成了大量测试图。
你发现他的图都满足一条特殊限制。设顶点 的入度和出度分别为 、,则
$$\sum_{i=1}^{n}|\mathrm{in}_i-\mathrm{out}_i|\le120.$$请利用这个限制解决问题:对每个顶点 ,求从 出发能够到达的不同顶点数 ,包括 自身。
输入格式
第一行两个整数 (,)。
接下来 行,每行两个整数 (),表示有一条从 到 的有向边。
保证上述度数差的绝对值之和不超过 120。允许重边,图不一定连通。重边仍是不同的边,因此应分别计入入度和出度;统计可达顶点时,每个顶点只计一次。
输出格式
输出一行 个整数,依次表示 。
样例 1
输入:
4 6
1 3
2 3
2 4
1 2
1 3
1 3
输出:
4 3 1 1
样例 2
输入:
5 7
1 4
1 5
1 2
2 4
3 4
2 5
1 4
输出:
4 3 2 1 1