本文主要是介绍codeforces 999E Reachability from the Capital，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：点击打开链接
题意：给你n个点，m条边，以及一个初始点s，问你至少还需要增加多少条边，使得初始点s与剩下其他的所有点都连通。
分析：
思路一：首先统计强连通分量，缩点并重新构图。除了s结点所在的连通分量，如果其他连通分量所构成的新点的入度为0，则使这个连通分量与s连通的最优的方案是将这个点与s结点相连。
思路二：先从起点搜索一遍，对不能到达的点加一条从首都到这个点的边（加边操作只能是思维上的，不能真的addedge(st, i)，因为后面还有删除边的操作），并标记，假如后加入的边能访问到先前的点，就删除原先对应加的边（说明允许犯错）。
思路三：染色，色块数减一（除去起点），感觉和思路二差不多。后面的染色可以覆盖之前的颜色。
代码一：（思路一）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<stack>
using namespace std;
#define N 5005
stack<int> sta;
vector<int> mp[N];
int dfn[N],low[N],vis[N],num[N],degree[N],in[N];
int n,m,s,cnt,id,ans;struct eg{int s,e;
}e[N];void init(){cnt=0;id=0;ans=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(vis,0,sizeof(vis));memset(num,0,sizeof(num));memset(degree,0,sizeof(degree));while(!sta.empty())sta.pop();for(int i=1;i<=n;i++)mp[i].clear();
}void tarjan(int x){///强连通 + 缩点dfn[x]=low[x]=++id;sta.push(x);vis[x]=1;for(int i=0;i<mp[x].size();i++){int t=mp[x][i];if(!dfn[t]) {tarjan(t);low[x]=min(low[x],low[t]);}else if(vis[t]) low[x]=min(low[x],dfn[t]);}if(dfn[x]==low[x]){int tp;cnt++;do{tp=sta.top();vis[tp]=0;num[tp]=cnt;sta.pop();}while(tp!=x);}
}int main(){while(cin>>n>>m>>s){init();for(int i=0;i<m;i++){cin>>e[i].s>>e[i].e;mp[e[i].s].push_back(e[i].e);}for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);for(int i=0;i<m;i++)///统计各个强连通分量的入度if(num[e[i].s]!=num[e[i].e])in[num[e[i].e]]++;for(int i=1;i<=cnt;i++)if(!in[i]&&num[s]!=i) ans++;///注意去掉起点所在强连通分量的入度cout<<ans<<endl;}
}代码二：（思路二）
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f
#define eps 1e-10
const int N = 5e3+10;int n,m,s;
bool vis[N],nd[N];///是否需要加边
vector<int> e[N];void dfs(int x) {vis[x]=1;nd[x]=0;for(int i=0;i<e[x].size();i++)if(!vis[e[x][i]]) dfs(e[x][i]);
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m>>s;for(int i=1;i<=m;i++) {int u,v;cin>>u>>v;e[u].pb(v);}for(int i=1;i<=n;i++) nd[i]=1;dfs(s);for(int i=1;i<=n;i++) {if(!nd[i]) continue;memset(vis,0,sizeof(vis));dfs(i);nd[i]=1;}int ans=0;for(int i=1;i<=n;i++) ans+=nd[i];cout<<ans<<endl;return 0;
}代码三：（思路三）
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f
#define eps 1e-10
const int N = 5e3+10;int n,m,s,c[N],ct[N];
bool vis[N];
vector<int> e[N];void dfs(int x,int color) {vis[x]=1,c[x]=color;for(int i=0;i<e[x].size();i++)if(c[e[x][i]]!=color) dfs(e[x][i],color);
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m>>s;for(int i=1;i<=m;i++) {int u,v;cin>>u>>v;if(v!=s) e[u].pb(v);}for(int i=1;i<=n;i++)if(!vis[i]) dfs(i,i);for(int i=1;i<=n;i++) ct[c[i]]=1;int ans=0;for(int i=1;i<=n;i++) ans+=ct[i];cout<<ans-1<<endl;return 0;
}这篇关于codeforces 999E Reachability from the Capital的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
