Minimum Edge Cut in a Multigraph
Autumn Tournament (2016)
Submission name: disconnect.cpp
Problem summary
Given an undirected multigraph without self-loops, find the minimum number of edges whose removal disconnects it. Parallel edges are separate edges; an already disconnected graph has answer0.
Source clarification. Official fixed-source maximum-flow reduction: https://infos.infosbg.com/files/Contests/ETI/2016/B/analyses/disconnect_analysis.pdf
Input
n, then m, then m pairs u v.
Output
The global minimum edge-cut size.
Constraints
2≤n≤100; 0≤m≤3000.
Worked example
Original statement sample.
Input
2 3 1 2 1 2 1 2
Output
3
Solution analysis
- Fix vertex1. For each other vertex t, find the minimum1–t cut. The minimum over these cuts is the global answer: every nontrivial cut separates1 from at least one vertex.
- Turn each undirected edge into one unit-capacity arc in each direction, keeping residual reverse arcs. A maximum-flow computation gives the corresponding minimum cut. Dinic repeatedly builds BFS levels and sends flow only along increasing levels, until the sink is unreachable.
- In the sample the three parallel edges all cross the only possible partition, so three units can flow and the cut size is3. If some t is unreachable before sending any flow, its cut is0 and no further computations can improve the answer.
Why it works
Any global cut separates the fixed source from a vertex t on its other side, so the1–t minimum cut is no larger than the global cut. Conversely every1–t cut is a valid nontrivial global cut, so none is smaller than the global optimum. Max-flow/min-cut supplies each pairwise value; taking their minimum is exact.
Watch out. Preserve parallel edges and both directions. Rebuild residual capacities for each sink. Do not return the smallest vertex degree: a cut between dense components can be smaller.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Any global cut separates the fixed source from a vertex t on its other side, so the1–t
// minimum cut is no larger than the global cut. Conversely every1–t cut is a valid nontrivial global
// cut, so none is smaller than the global optimum.
#include<algorithm>
#include<iostream>
#include<limits>
#include<queue>
#include<utility>
#include<vector>
using namespace std;
struct Edge{
int to;
int reverse;
int capacity;
};
class Dinic{
vector<vector<Edge>>graph;
vector<int>level;
vector<int>current;
public:
explicit Dinic(int n):graph(n),level(n),current(n){
}
void add(int from,int to){
Edge forward{to,static_cast<int>(graph[to].size()),1};
Edge reverse{from,static_cast<int>(graph[from].size()),0};
graph[from].push_back(forward);
graph[to].push_back(reverse);
}
bool bfs(int source,int sink){
fill(level.begin(),level.end(),-1);
queue<int>pending;
pending.push(source);
level[source]=0;
while(!pending.empty()){
int from=pending.front();
pending.pop();
for(const Edge&edge:graph[from]){
if(edge.capacity>0&&level[edge.to]==-1){
level[edge.to]=level[from]+1;
pending.push(edge.to);
}
}
}
return level[sink]!=-1;
}
int send(int from,int sink,int amount){
if(from==sink){
return amount;
}
for(int&index=current[from];index<static_cast<int>(graph[from].size());index++){
Edge&edge=graph[from][index];
if(edge.capacity>0&&level[edge.to]==level[from]+1){
int pushed=send(edge.to,sink,min(amount,edge.capacity));
if(pushed>0){
edge.capacity-=pushed;
graph[edge.to][edge.reverse].capacity+=pushed;
return pushed;
}
}
}
return 0;
}
int flow(int source,int sink){
int result=0;
while(bfs(source,sink)){
fill(current.begin(),current.end(),0);
while(int pushed=send(source,sink,3001)){
result+=pushed;
}
}
return result;
}
};
int main(){
int n,m;
cin>>n>>m;
vector<pair<int,int>>edges(m);
for(auto&edge:edges){
cin>>edge.first>>edge.second;
}
int answer=m;
for(int sink=2;sink<=n;sink++){
Dinic network(n+1);
for(auto[u,v]:edges){
network.add(u,v);
network.add(v,u);
}
answer=min(answer,network.flow(1,sink));
if(answer==0){
break;
}
}
cout<<answer<<'\n';
}