草庐IT

[JSOI2010]连通数

传送地址:https://www.luogu.com.cn/problem/P4306题目描述度量一个有向图连通情况的一个指标是连通数,指图中可达顶点对个的个数。如图顶点 11 可达 1,2,3,4,51,2,3,4,5顶点 22 可达 2,3,4,52,3,4,5顶点 33 可达 3,4,53,4,5顶点 4,54,5 都只能到达自身。所以这张图的连通数为 1414。给定一张图,请你求出它的连通数 题解这题打了半天,发现用dfs或者bfs都是会TLE于是就想采用另一种方法:bitset 这样我们就可以用0代表不能到达,1代表可以到达最后对对可以到的的进行求和即可另外,关于bitset的使用以

[JSOI2010]连通数

传送地址:https://www.luogu.com.cn/problem/P4306题目描述度量一个有向图连通情况的一个指标是连通数,指图中可达顶点对个的个数。如图顶点 11 可达 1,2,3,4,51,2,3,4,5顶点 22 可达 2,3,4,52,3,4,5顶点 33 可达 3,4,53,4,5顶点 4,54,5 都只能到达自身。所以这张图的连通数为 1414。给定一张图,请你求出它的连通数 题解这题打了半天,发现用dfs或者bfs都是会TLE于是就想采用另一种方法:bitset 这样我们就可以用0代表不能到达,1代表可以到达最后对对可以到的的进行求和即可另外,关于bitset的使用以