Snowfall and Dangerous Cities
National Olympiad — National round (2018 season)
Submission name: Snowfall.cpp
Problem summary
A road closes once snowfall reaches its threshold. A city is dangerous exactly when the remaining road graph is connected and removing that city disconnects two other cities. Find the smallest nonnegative snowfall making at least K cities dangerous, or report impossibility.
Input
N M K, then M roads u v threshold. Parallel roads and loops are allowed.
Output
Snowfall X and dangerous count Y, then their increasing labels; if impossible print −1 0.
Constraints
2 ≤ N ≤ 50,000; 1 ≤ M ≤ 200,000; 1 ≤ K ≤ N; 1 ≤ threshold ≤ 10⁹; the zero-snow graph is connected.
Worked example
An independently prepared example for this explanation.
Input
8 13 3 1 2 19 1 3 13 2 3 5 4 2 9 2 5 7 3 5 17 6 3 8 3 8 12 4 7 11 5 7 5 7 2 10 7 6 13 8 5 16
Output
8 4 1 2 3 7
Solution analysis
- For a fixed snowfall keep edges with threshold greater than it. Run an iterative DFS computing discovery times and low links. A nonroot vertex is an articulation point if a DFS child cannot reach a strict ancestor; a root needs at least two DFS children.
- As long as the graph stays connected, deleting edges cannot make an existing articulation point cease to be one. Once disconnected it never reconnects. Hence the predicate “graph disconnected OR at least K articulation points” is monotone and can be binary-searched over snowfall 0…10⁹.
- At the first true value, run the check again. If connected, its articulation points are the required answer. If disconnected, the threshold was reached before enough dangerous cities appeared, so there is no answer. In the example the count jumps from one at snowfall 7 to four at snowfall 8.
Why it works
The DFS low-link criterion exactly characterizes articulation points in an undirected graph. While connected, removal of an articulation vertex already separates a pair; deleting further edges cannot restore a path between that pair. Connectivity loss is permanent as well, proving monotonicity of the augmented predicate. Binary search finds its first true value. A disconnected first-true graph implies all earlier connected states had fewer than K points, and all later states have no dangerous cities under the definition. Otherwise the returned connected state is the earliest valid one.
Watch out. A disconnected graph has zero dangerous cities, which makes direct count-only binary search invalid. Skip the parent edge by its unique edge ID, not by parent vertex, to handle parallel roads. Snowfall zero can already be the answer.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<numeric>
#include<vector>
// Algorithm: For a fixed snowfall keep edges with threshold greater than it.
using namespace std;
struct Edge{
int to,threshold,id;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,k;
cin>>n>>m>>k;
vector<vector<Edge>>adjacent(n);
for(int id=0;id<m;id++){
int u,v,threshold;
cin>>u>>v>>threshold;
adjacent[--u].push_back({--v,threshold,id});
adjacent[v].push_back({u,threshold,id});
}
vector<bool>dangerous;
auto inspect=[&](int snow){
vector<int>discovery(n),low(n),parent(n,-1),parentEdge(n,-1),next(n),children(n);
dangerous.assign(n,false);
vector<int>stack(1,0);
int timer=1;
discovery[0]=low[0]=timer;
while(!stack.empty()){
int u=stack.back();
if(next[u]<static_cast<int>(adjacent[u].size())){
Edge edge=adjacent[u][next[u]++];
if(edge.threshold<=snow||edge.id==parentEdge[u]){
continue;
}
int v=edge.to;
if(!discovery[v]){
parent[v]=u;
parentEdge[v]=edge.id;
children[u]++;
discovery[v]=low[v]=++timer;
stack.push_back(v);
}
else{
low[u]=min(low[u],discovery[v]);
}
}
else{
stack.pop_back();
int p=parent[u];
if(p==-1){
dangerous[u]=children[u]>1;
}
else{
low[p]=min(low[p],low[u]);
if(parent[p]!=-1&&low[u]>=discovery[p]){
dangerous[p]=true;
}
}
}
}
if(timer!=n){
return -1;
}
return accumulate(dangerous.begin(),dangerous.end(),0);
};
int left=0;
int right=1000000000;
while(left<right){
int middle=left+(right-left)/2;
int count=inspect(middle);
if(count==-1||count>=k){
right=middle;
}
else{
left=middle+1;
}
}
int count=inspect(left);
if(count<k){
cout<<"-1 0\n";
return 0;
}
cout<<left<<' '<<count<<'\n';
bool first=true;
for(int u=0;u<n;u++){
if(dangerous[u]){
cout<<(first?"":" ")<<u+1;
first=false;
}
}
cout<<'\n';
}