Codeforce 999 E. Reachability from the Capital 解析(思維、SCC)

今天我們來看看CF999E
題目連結

題目
給一個有向圖，和一個點$s$。求至少要蓋幾條路才能夠從$s$到所有點。

前言

這題之前在Youtube上看到過了，結果還是寫了好久，主要是第一次寫SCC。

想法

我們能夠找出所有強連通分量，然後紀錄每個分量的入度。入度為零的分量就必須從$s$連一條邊過去。(如果$s$所在分量的入度為零，解答要減$1$)

程式碼:

const int _n=5010;  
int t,n,m,s,u,v,in[_n],scc[_n],T;  
stack<int> st;  
VI G1[_n],G2[_n]/*,G3[_n]*/;  
bool vis[_n];  
void dfs1(int v){  
  vis[v]=1;  
  for(int u:G2[v])if(!vis[u])dfs1(u);  
  st.push(v);  
}  
void dfs2(int v){  
  vis[v]=1,scc[v]=T;  
  for(int u:G1[v])if(!vis[u])dfs2(u);  
}  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n>>m>>s;rep(i,0,m){cin>>u>>v;G1[u].pb(v),G2[v].pb(u);}  
  rep(i,1,n+1)if(!vis[i])dfs1(i); memset(vis,0,sizeof vis);  
  while(!st.empty()){  
    if(!vis[st.top()])T++,dfs2(st.top());  
    st.pop();  
  }//下面一行是建縮點後的圖，這題(999E)不用真的把圖建起來，所以註解掉G3[i].pb(u)  
  rep(i,1,n+1)for(int u:G1[i])if(scc[i]!=scc[u])/*G3[i].pb(u),*/in[scc[u]]++;  
  int ans=0;rep(i,0,T)if(!in[i])ans++;  
  cout<<ans-(in[scc[s]]==0)<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看
Submission