First Road Failure Separating Two Cities
Autumn Tournament (2022)
Submission name: connect.cpp
Problem summary
For each city pair, determine whether both directions are reachable initially, and find the smallest input edge whose deletion destroys that mutual reachability. Return0 if initially disconnected and M+1 if no single deletion separates them. Encode the whole answer sequence in base200000 modulo1000000007. Q=0 requests all unordered pairs including equal cities in lexicographic order.
Source clarification. The O(N)-candidate two-tree certificate and lexicographic-row optimization follow the official full-score editorial: https://infos.infosbg.com/files/Contests/ETI/2022/B/analyses/B4_connect_analysis.pdf
Input
N M; M directed edges; Q; then Q pairs if Q>0.
Output
The modular base200000 encoding of the query answers.
Constraints
2≤N≤2000;1≤M≤100000;0≤Q≤100000; parallel directed edges are allowed.
Worked example
Original statement sample.
Input
6 11 1 4 4 3 3 5 5 1 1 3 3 6 5 6 6 2 4 2 5 1 3 5 0
Output
575589257
Solution analysis
- Find the original strongly connected components. Inside each component, choose one directed spanning tree from a root and another from the same root in the reversed graph. Their union preserves strong connectivity: any vertex can reach the root and the root can reach any vertex.
- Therefore an edge outside those trees cannot be the first damaging deletion. At most2N−2 candidate edges remain. Sort their original input IDs. For each candidate deletion, recompute SCC labels and store a row of labels for every vertex; two vertices are separated exactly when their rows first differ.
- Sort these label rows lexicographically, keeping the original SCC label as the first key. For any two sorted rows, the first differing column is the minimum of the first-difference positions between consecutive rows in their interval. Compute adjacent separators, then all pair answers with running minima in O(N²). The sample’s ordered answers are12,0,12,1,12,0,12,0,0,0,0,12,1,12,0,12,1,0,12,0,12; rolling base200000 encoding gives575589257.
Why it works
Every noncandidate deletion leaves both chosen trees intact, so it preserves every original SCC. Candidate SCC columns therefore contain all possible separating deletions. For lexicographically sorted rows, a common prefix extends across an interval exactly when every adjacent pair shares that prefix; hence the earliest differing column for interval endpoints is the minimum adjacent separator. Original SCC changes use separator0, and identical rows use M+1, yielding exactly the specified answers.
Watch out. Use edge IDs, not endpoint pairs, when skipping one edge: parallel roads remain distinct. A vertex is always mutually reachable with itself, so its answer is M+1. Candidate columns must be ordered by input ID. Never try all M deletions when M is100000.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every noncandidate deletion leaves both chosen trees intact, so it preserves every
// original SCC. Candidate SCC columns therefore contain all possible separating deletions.
#include<algorithm>
#include<iostream>
#include<numeric>
#include<utility>
#include<vector>
using namespace std;
class Graph{
public:
int n;
vector<vector<pair<int,int>>>forward;
vector<vector<pair<int,int>>>reverse;
vector<int>component;
vector<char>seen;
vector<int>order;
explicit Graph(int size):n(size),forward(n),reverse(n),component(n),seen(n){
}
void first(int vertex,int removed){
seen[vertex]=true;
for(auto[next,edge]:forward[vertex]){
if(edge!=removed&&!seen[next]){
first(next,removed);
}
}
order.push_back(vertex);
}
void second(int vertex,int removed,int label){
component[vertex]=label;
for(auto[next,edge]:reverse[vertex]){
if(edge!=removed&&component[next]==-1){
second(next,removed,label);
}
}
}
void components(int removed){
fill(seen.begin(),seen.end(),false);
fill(component.begin(),component.end(),-1);
order.clear();
for(int vertex=0;vertex<n;vertex++){
if(!seen[vertex]){
first(vertex,removed);
}
}
int label=0;
for(auto it=order.rbegin();it!=order.rend();++it){
if(component[*it]==-1){
second(*it,removed,label++);
}
}
}
void tree(int vertex,bool backwards,const vector<int>&original,vector<char>&chosen){
seen[vertex]=true;
const auto&edges=backwards?reverse[vertex]:forward[vertex];
for(auto[next,edge]:edges){
if(original[next]==original[vertex]&&!seen[next]){
chosen[edge]=true;
tree(next,backwards,original,chosen);
}
}
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
Graph graph(n);
for(int edge=1;edge<=m;edge++){
int a,b;
cin>>a>>b;
a--;
b--;
graph.forward[a].push_back({b,edge});
graph.reverse[b].push_back({a,edge});
}
graph.components(-1);
vector<int>original=graph.component;
vector<char>chosen(m+1,false);
for(bool backwards:{false,true}){
fill(graph.seen.begin(),graph.seen.end(),false);
for(int vertex=0;vertex<n;vertex++){
if(!graph.seen[vertex]){
graph.tree(vertex,backwards,original,chosen);
}
}
}
vector<int>candidates;
for(int edge=1;edge<=m;edge++){
if(chosen[edge]){
candidates.push_back(edge);
}
}
int columns=static_cast<int>(candidates.size());
vector<unsigned short>labels(n*columns);
for(int column=0;column<columns;column++){
graph.components(candidates[column]);
for(int vertex=0;vertex<n;vertex++){
labels[vertex*columns+column]=static_cast<unsigned short>(graph.component[vertex]);
}
}
vector<int>sorted(n);
iota(sorted.begin(),sorted.end(),0);
sort(sorted.begin(),sorted.end(),[&](int a,int b){
if(original[a]!=original[b]){
return original[a]<original[b];
}
for(int column=0;column<columns;column++){
int x=labels[a*columns+column];
int y=labels[b*columns+column];
if(x!=y){
return x<y;
}
}
return a<b;
});
vector<int>separator(n-1,m+1);
for(int i=1;i<n;i++){
int a=sorted[i-1];
int b=sorted[i];
if(original[a]!=original[b]){
separator[i-1]=0;
continue;
}
for(int column=0;column<columns;column++){
if(labels[a*columns+column]!=labels[b*columns+column]){
separator[i-1]=candidates[column];
break;
}
}
}
vector<int>answer(n*n,m+1);
for(int left=0;left<n;left++){
int minimum=m+1;
for(int right=left+1;right<n;right++){
minimum=min(minimum,separator[right-1]);
answer[sorted[left]*n+sorted[right]]=minimum;
answer[sorted[right]*n+sorted[left]]=minimum;
}
}
const long long modulo=1000000007;
long long encoded=0;
auto append=[&](int a,int b){
encoded=(encoded*200000+answer[a*n+b])%modulo;
};
int q;
cin>>q;
if(q==0){
for(int a=0;a<n;a++){
for(int b=a;b<n;b++){
append(a,b);
}
}
}
else{
while(q--){
int a,b;
cin>>a>>b;
append(a-1,b-1);
}
}
cout<<encoded<<'\n';
}