[CF999E]Reachability from the Capital

2021-07-08 07:16

阅读：659

标签：col bool bsp size cst clu from oid 起点

题目大意：有一个$n$个点$m$条边的有向图，起点$S$，要求你添加最少的边使得$S$可以到达所有点

题解：缩点，答案就是没有入边的强连通分量个数，注意，如果起点$S$所在的强连通块没有入边则不计入答案

卡点：无

C++ Code：

#include 
#define maxn 5010
#define maxm 5010
int head[maxn], cnt;
struct Edge {
	int from, to, nxt;
} e[maxm];
inline void add(int a, int b) {
	e[++cnt] = (Edge) {a, b, head[a]}; head[a] = cnt;
}

int DFN[maxn], low[maxn], idx;
int S[maxn], top, res[maxn], CNT;
bool ins[maxn];
inline int min(int a, int b) {return a

[CF999E]Reachability from the Capital

标签：col bool bsp size cst clu from oid 起点

原文地址：https://www.cnblogs.com/Memory-of-winter/p/9744793.html

上一篇：MVC模型注解

下一篇：Win10下安装zookeeper

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[CF999E]Reachability from the Capital
文章链接：http://soscw.com/essay/102300.html

亲，登录后才可以留言！

[CF999E]Reachability from the Capital

评论

热门文章

推荐文章

最新文章

置顶文章