Make Every Vertex Reachable
National Olympiad — Regional round
Submission name: reach.cpp
Problem summary
Given a directed graph and a designated vertex s, add as few directed edges as possible so that every other vertex is reachable from s. Vertices are numbered 0 through n−1.
Input
n m s, followed by m pairs u v describing directed edges u→v.
Output
The minimum number of added edges.
Constraints
0<n<50,000; 0<m<200,000.
Worked example
An independently prepared example for this explanation.
Input
4 2 0 0 1 2 3
Output
1
Solution analysis
- Find strongly connected components, then mark the components already reachable from s.
- In the subgraph induced by the remaining components, count components with no incoming edge from another remaining component. Add an edge from s to one vertex of each such source component.
Why it works
Every unreachable source component needs a new incoming edge: existing edges cannot enter it from another unreachable component, and a reachable predecessor would already make it reachable. These requirements are distinct. Conversely, every vertex of a finite DAG descends from a source, so connecting all these sources reaches all components and attains the lower bound.
Watch out. The input uses 0-based labels. Counting weakly connected components or all unreachable SCCs is incorrect. Use iterative DFS to avoid a deep recursion stack.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every unreachable source component needs a new incoming edge: existing edges cannot enter
// it from another unreachable component, and a reachable predecessor would already make it reachable.
// These requirements are distinct.
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,s;
cin>>n>>m>>s;
vector<vector<int>>g(n),r(n);
vector<pair<int,int>>edges;
while(m--){
int u,v;
cin>>u>>v;
g[u].push_back(v);
r[v].push_back(u);
edges.push_back({u,v});
}
vector<int>seen(n),order;
for(int root=0;root<n;root++){
if(!seen[root]){
vector<pair<int,int>>st={{root,0}};
seen[root]=1;
while(!st.empty()){
int v=st.back().first,&p=st.back().second;
if(p==(int)g[v].size()){
order.push_back(v);
st.pop_back();
}
else{
int u=g[v][p++];
if(!seen[u]){
seen[u]=1;
st.push_back({u,0});
}
}
}
}
}
vector<int>comp(n,-1);
int C=0;
reverse(order.begin(),order.end());
for(int v:order){
if(comp[v]<0){
vector<int>st={v};
comp[v]=C;
while(!st.empty()){
int u=st.back();
st.pop_back();
for(int w:r[u]){
if(comp[w]<0){
comp[w]=C;
st.push_back(w);
}
}
}
C++;
}
}
fill(seen.begin(),seen.end(),0);
vector<int>st={s};
seen[s]=1;
while(!st.empty()){
int v=st.back();
st.pop_back();
for(int u:g[v]){
if(!seen[u]){
seen[u]=1;
st.push_back(u);
}
}
}
vector<int>reachable(C),incoming(C);
for(int v=0;v<n;v++){
if(seen[v]){
reachable[comp[v]]=1;
}
}
for(auto[u,v]:edges){
if(comp[u]!=comp[v]&&!reachable[comp[u]]&&!reachable[comp[v]]){
incoming[comp[v]]=1;
}
}
int answer=0;
for(int c=0;c<C;c++){
answer+=!reachable[c]&&!incoming[c];
}
cout<<answer<<'\n';
}