[CF999E] Reachability from the Capital - 强连通分量

2021-03-12 18:27

阅读：2045

标签：pre efi amp define c++ cap ons name code

有 \(n\) 座城市和 \(m\) 条单向道路，为了能让首都能够到达所有的城市，最少需要新修建多少新的单向道路？

Solution

答案为缩点后的分量图中除 \(S\) 所在分量外入度为 \(0\) 的分量数

#include 
using namespace std;

#define int long long
const int N = 1000005;

namespace scc {
    vector  g[N],scc[N];
    int ind,f[N],siz[N],dfn[N],low[N],vis[N],s[N],
        bel[N],top,tot,n,m,d[N];
    void make(int p,int q) {
        g[p].push_back(q);
    }
    void dfs(int p) {
        s[++top]=p;
        dfn[p]=low[p]=++ind;
        for(int i=0;i>n>>m>>r;
    for(int i=1;i>t1>>t2;
        make(t1,t2);
    }
    scc::solve(n);
    for(int i=1;i

[CF999E] Reachability from the Capital - 强连通分量

标签：pre efi amp define c++ cap ons name code

原文地址：https://www.cnblogs.com/mollnn/p/12585933.html

上一篇：（2）Windows PowerShell使用

下一篇：winform折叠菜单

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

亲，登录后才可以留言！

[CF999E] Reachability from the Capital - 强连通分量

Solution

评论

热门文章

推荐文章

最新文章

置顶文章