题目链接:
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("%d\n",ans); return 0; }