题解 P7251 【[JSOI2014] 强连通图】

· · 题解

P7251 [JSOI2014] 强连通图

题目大意：

给定个图，回答两个问题：

  1. 求图中最大的强连通分量的大小
  2. 求添加多少条边可使图强连通。

    solution:

    $\max \limits_{i=1}^{cnt\_scc}\{\text{size[ i ]}\}$ 。考虑 $2$ 。一个强连通图必然没有入度为 $0$ 和出度为 $0$ 的点(点数大于 $1$ )，在缩点后，我们只需要统计入度和出度为 $0$ 的**强连通分量**的个数再取个 $\max$ 就好了。 ## 接下来是细节的处理： 在上文叙述中括号中的条件需要特判，即 $\text{cnt\_scc}==1$ 时，最大的强连通分量大小只有 $1$ 且不用加边即是强连通图。输出: ``` 1 0 ``` 看到这的同学，可以自己去写代码了(~~tf口吻~~)

code

End

作者的碎碎念：

有用留赞(言简意赅)