E. Reachability from the Capital
这个题目就是给你一个有向图，给你起点，问增加多少条边让这个图变成一个连通图。
这个因为n只有5000m只有5000
所以可以暴力枚举这个n，用n*n的复杂度过去。
#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <stack> #include <bitset> #include <vector> #include <map> #include <string> #include <cstring> #include <bitset> using namespace std; const int maxn=5e3+10; vector<int>G[maxn]; bool vis[maxn]; bool cnt[maxn]; int ans=0; void dfs(int u,int f){ ans++; vis[u]=1; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==f||vis[v]) continue; dfs(v,u); } } int num; void DFS(int u,int f){ if(vis[u]) return ; num++; cnt[u]=1; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==f||vis[v]||cnt[v]) continue; DFS(v,u); } } vector<int>a; int main(){ int n,m,s; scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); } dfs(s,-1); for(int i=1;i<=n;i++){ if(!vis[i]) a.push_back(i); } int res=0; while(ans<n){ int maxs=0,id=-1; for(int i=0;i<a.size();i++){ memset(cnt,0,sizeof(cnt)); num=0; int x=a[i]; DFS(x,-1); if(num>maxs) maxs=num,id=x; } if(id==-1) break; res++; dfs(id,-1); } printf("%d ",res); return 0; }
#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <stack> #include <bitset> #include <vector> #include <map> #include <string> #include <cstring> #include <bitset> using namespace std; const int maxn=5e3+10; vector<int>G[maxn]; bool vis[maxn]; bool cnt[maxn]; int ans=0; void dfs(int u,int f){ ans++; vis[u]=1; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==f||vis[v]) continue; dfs(v,u); } } int num; void DFS(int u,int f){ if(vis[u]) return ; num++; cnt[u]=1; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==f||vis[v]||cnt[v]) continue; DFS(v,u); } } void dfs2(int u,int f){ if(vis[u]) return ; cnt[u]=0; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==f||vis[v]||cnt[v]==0) continue; dfs2(v,u); } } vector<int>a; int main(){ int n,m,s; scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); } dfs(s,-1); for(int i=1;i<=n;i++){ if(!vis[i]) a.push_back(i); } int res=0; while(ans<n){ int maxs=0,id=-1; for(int i=0;i<a.size();i++){ num=0; int x=a[i]; DFS(x,-1); dfs2(x,-1); if(num>maxs) maxs=num,id=x; } if(id==-1) break; res++; dfs(id,-1); } printf("%d ",res); return 0; }
#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <stack> #include <bitset> #include <vector> #include <map> #include <string> #include <cstring> #include <bitset> using namespace std; const int maxn=5e3+10; vector<int>G[maxn]; bool vis[maxn]; bool cnt[maxn]; int ans=0; void dfs(int u,int f){ ans++; vis[u]=1; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==f||vis[v]) continue; dfs(v,u); } } int num; void DFS(int u,int f){ if(vis[u]) return ; num++; cnt[u]=1; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==f||vis[v]||cnt[v]) continue; DFS(v,u); } } void dfs2(int u,int f){ if(vis[u]) return ; cnt[u]=0; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==f||vis[v]||cnt[v]==0) continue; dfs2(v,u); } } vector<int>a; int main(){ int n,m,s; scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); } dfs(s,-1); for(int i=1;i<=n;i++){ if(!vis[i]) a.push_back(i); } int res=0; while(ans<n){ int maxs=0,id=-1; for(int i=0;i<a.size();i++){ num=0; int x=a[i]; DFS(x,-1); dfs2(x,-1); if(num>maxs) maxs=num,id=x; } if(id==-1) break; res++; dfs(id,-1); } printf("%d ",res); return 0; }