codeforces#999 E. Reachability from the Capital（图论加边）

发布时间：2020-12-14 05:10:49 所属栏目：大数据来源：网络整理

导读：题目链接： https://codeforces.com/contest/999/problem/E 题意：在有向图中加边，让$S$点可以到达所有点数据范围： $ 1 leq n leq 5000$ 分析：? 先从$S$点出发，所有不可达点标记一下如果某个不可达点可以被另一个不可达点到达，那么把这个不可达点

题目链接：

https://codeforces.com/contest/999/problem/E

题意：

在有向图中加边，让$S$点可以到达所有点

数据范围：

$ 1 leq n leq 5000$

分析：?

先从$S$点出发，所有不可达点标记一下

如果某个不可达点可以被另一个不可达点到达，那么把这个不可达点标记为可达

最后计算不可达点的数量

去年做过的题目，今年反而不会写了

ac代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 5e3 + 5;
ll mod =  998244353;
vector<int>ve[maxn];
int vis[maxn],fla[maxn];
void dfs(int x){
    vis[x]=1;
    for(int i=0;i<ve[x].size();i++){
        int v=ve[x][i];
        if(vis[v]==0)dfs(v);
    }
}
int main()
{
    int n,m,s,ans=0;
    scanf("%d %d %d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        ve[a].push_back(b);
    }
    dfs(s);
    for(int i=1;i<=n;i++)
        if(vis[i]==0)fla[i]=1;
    for(int i=1;i<=n;i++){
        if(fla[i]==0)continue;
        for(int j=1;j<=n;j++)vis[j]=0;
        dfs(i);
        for(int j=1;j<=n;j++)
            if(j!=i&&vis[j])fla[j]=0;
    }
    for(int i=1;i<=n;i++)if(fla[i])ans++;
    printf("%dn",ans);
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!