Winter
National Olympiad — Regional round (2020 season)
Submission name: winter.cpp
Problem summary
In a connected undirected graph, count unordered pairs of distinct vertices that remain connected after deletion of any single edge.
Input
N M, followed by M endpoint pairs for undirected streets.
Output
The number of eligible vertex pairs.
Constraints
1 ≤ N ≤ 100,000; 1 ≤ M ≤ 200,000; the graph is connected.
Worked example
Official sample, transcribed with whitespace restored from the PDF.
Input
5 5 1 2 2 3 3 1 2 4 2 5
Output
3
Solution analysis
- An edge whose removal disconnects the graph is a bridge. Delete all bridges; vertices within one remaining connected component stay mutually reachable after any single-edge failure. Vertices in different components are separated by some bridge and cannot qualify.
- Find bridges by depth-first discovery times tin and low values. A DFS tree edge parent→v is a bridge exactly when low[v]>tin[parent]. Use an explicit vertex stack and per-vertex adjacency cursor so a path of length 100,000 cannot overflow the process call stack. Track parent edge identifiers, which also handles parallel edges correctly.
- Flood-fill the graph while ignoring bridges. A component of size c contributes c(c−1)/2 pairs. In the sample the triangle {1,2,3} is one component, and vertices 4 and 5 each stand alone, so the answer is three.
Why it works
The low-link criterion identifies exactly those tree edges with no alternate return edge from their descendant subtree, hence exactly the bridges. Nonbridge edges lie on cycles and cannot disconnect any vertices when removed. Consequently the components after removing all bridges are precisely the equivalence classes of vertices connected despite every single-edge deletion. Summing unordered pair counts within these disjoint classes counts all and only valid pairs.
Watch out. The objects are unordered distinct pairs. Use edge IDs rather than skipping every edge to the parent. The answer may exceed 32-bit range.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The low-link criterion identifies exactly those tree edges with no alternate return edge
// from their descendant subtree, hence exactly the bridges. Nonbridge edges lie on cycles and cannot
// disconnect any vertices when removed.
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<vector<pair<int,int>>>graph(n);
for(int id=0;id<m;++id){
int u,v;
cin>>u>>v;
--u;
--v;
graph[u].push_back({v,id});
graph[v].push_back({u,id});
}
vector<int>tin(n,-1),low(n),parent(n,-1),parentEdge(n,-1),next(n);
vector<bool>bridge(m,false);
int timer=0;
for(int start=0;start<n;++start){
if(tin[start]!=-1){
continue;
}
vector<int>stack={start};
tin[start]=low[start]=timer++;
while(!stack.empty()){
int v=stack.back();
if(next[v]==int(graph[v].size())){
stack.pop_back();
if(parent[v]!=-1){
int p=parent[v];
low[p]=min(low[p],low[v]);
bridge[parentEdge[v]]=low[v]>tin[p];
}
continue;
}
auto[u,id]=graph[v][next[v]++];
if(id==parentEdge[v]){
continue;
}
if(tin[u]==-1){
parent[u]=v;
parentEdge[u]=id;
tin[u]=low[u]=timer++;
stack.push_back(u);
}
else{
low[v]=min(low[v],tin[u]);
}
}
}
vector<bool>visited(n,false);
long long answer=0;
for(int start=0;start<n;++start){
if(visited[start]){
continue;
}
vector<int>stack={start};
visited[start]=true;
long long count=0;
while(!stack.empty()){
int v=stack.back();
stack.pop_back();
++count;
for(auto[u,id]:graph[v]){
if(!bridge[id]&&!visited[u]){
visited[u]=true;
stack.push_back(u);
}
}
}
answer+=count*(count-1)/2;
}
cout<<answer<<'\n';
}