Fastest Broadcast Sources
National Olympiad — Regional round
Submission name: cnet.cpp
Problem summary
A directed network has vertices 0 through N−1. A message propagates along every outgoing edge in one time unit, in parallel. Find all starting vertices that reach the entire network in the smallest possible time among such vertices.
Input
N M, followed by M directed edges sender receiver.
Output
The number of optimal starting vertices, then their indices in ascending order.
Constraints
1 < N ≤ 3000; 1 < M ≤ 400000. For N>500, only 10% of the computers can be starting computers, as stated by the source.
Worked example
An independently prepared example for this explanation.
Input
3 3 0 1 1 2 2 1
Output
1 0
Solution analysis
- Compute strongly connected components with Kosaraju. A universal source must belong to the unique zero-indegree component of the condensation DAG; if there is more than one such component there is no universal source.
- Run BFS from each vertex of that component. Its completion time is the largest BFS distance.
- Keep all vertices attaining the smallest completion time. The source restriction limits the candidate component on large instances.
Why it works
Every component must be reachable from a universal source, so its component is the unique source in the DAG. Conversely a finite DAG with one source has every vertex reachable from it. BFS computes shortest arrival times; their maximum is the broadcast completion time. Minimizing it gives exactly the requested sources.
Watch out. Edges are directed and vertex labels start at zero. Merely finding vertices that can reach everyone misses the minimum-time condition.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every component must be reachable from a universal source, so its component is the unique
// source in the DAG. Conversely a finite DAG with one source has every vertex reachable from it.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<utility>
#include<tuple>
#include<functional>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<vector<int>>g(n),rg(n);
vector<pair<int,int>>edges;
while(m--){
int u,v;
cin>>u>>v;
g[u].push_back(v);
rg[v].push_back(u);
edges.push_back({u,v});
}
vector<int>seen(n),order,comp(n,-1);
function<void(int)>dfs=[&](int v){
seen[v]=1;
for(int u:g[v]){
if(!seen[u]){
dfs(u);
}
}
order.push_back(v);
};
for(int i=0;i<n;i++){
if(!seen[i]){
dfs(i);
}
}
function<void(int,int)>mark=[&](int v,int c){
comp[v]=c;
for(int u:rg[v]){
if(comp[u]<0){
mark(u,c);
}
}
};
int cc=0;
reverse(order.begin(),order.end());
for(int v:order){
if(comp[v]<0){
mark(v,cc++);
}
}
vector<int>indeg(cc);
for(auto[u,v]:edges){
if(comp[u]!=comp[v]){
indeg[comp[v]]++;
}
}
int source=-1;
for(int c=0;c<cc;c++){
if(!indeg[c]){
if(source!=-1){
cout<<0<<"\n\n";
return 0;
}
source=c;
}
}
vector<int>ans;
int best=n;
for(int s=0;s<n;s++){
if(comp[s]==source){
vector<int>d(n,-1);
queue<int>q;
q.push(s);
d[s]=0;
int ecc=0;
while(!q.empty()){
int v=q.front();
q.pop();
for(int u:g[v]){
if(d[u]<0){
d[u]=d[v]+1;
ecc=max(ecc,d[u]);
q.push(u);
}
}
}
if(ecc<best){
best=ecc;
ans.clear();
}
if(ecc==best){
ans.push_back(s);
}
}
}
cout<<ans.size()<<'\n';
for(int v:ans){
cout<<v<<' ';
}
cout<<'\n';
}