Recoloring a Complete Graph
Autumn Tournament (2017)
Submission name: colorgraph.cpp
Problem summary
Every pair of distinct vertices has one red or blue edge. A color is connected when its edges connect all vertices. Given the desired red/blue connectivity bits (A,B), flip as few edge colors as possible and output the flipped pairs, or report impossibility.
Input
N, followed by an N×N symmetric matrix (0 red, 1 blue; diagonal ignored), then A B.
Output
Print -1 if impossible; otherwise the minimum count and that many endpoint pairs. Any optimal solution is accepted.
Constraints
3 ≤ N ≤ 250; A,B are 0 or 1.
Worked example
The third official example, with whitespace restored from the PDF.
Input
3 0 1 1 1 0 0 1 0 0 0 1
Output
0
Solution analysis
- A graph and its complement cannot both be disconnected: vertices in different components of one color have all cross-edges in the other color. Thus (0,0) is impossible. With three vertices, (1,1) is also impossible because two spanning connected graphs would require at least four edges, but only three exist.
- To make one color disconnected, choose a partition and flip every edge of that color crossing it. The least number is precisely its global minimum cut. Stoer–Wagner finds this cut in cubic time by repeatedly growing a maximum-adjacency ordering, recording its last-vertex cut, and merging the last two supervertices. Store the original vertices in every merged group so the cut can be reconstructed. The complement is then automatically connected.
- To make both colors connected, suppose the missing color has c components. A flip can merge at most two, so c−1 is a lower bound. Repeatedly merge two of those components using an edge that is not a bridge of the currently connected color. Removing a non-bridge keeps that color connected. For a complete two-colored graph this succeeds with c−1 flips except when the disconnected color is a clique plus one isolated vertex. In that exceptional case its complement is a star: one flip cannot preserve both connectivities, and two flips suffice.
- For that star exception, join its isolated vertex p to a clique vertex q, and recolor q−r in the opposite direction for another clique vertex r. At least three clique vertices exist because N≥4. Worked example: the sample already has red components {1},{2,3}, and blue edges 1−2,1−3, so its requested state (0,1) needs zero flips. A four-vertex blue triangle plus an isolated vertex needs exactly two flips to obtain (1,1).
Why it works
The minimum-cut case is necessary because every disconnected result defines a cut whose original same-color edges must all be flipped, and sufficient by flipping a minimum cut. In the both-connected case, c−1 is necessary; the bridge-preserving merge attains it outside the star exception. If every cross-component edge were a bridge, completeness forces precisely that exceptional star (or the excluded three-vertex case). A merge from three or more components cannot create this exception: a newly merged complete clique component of size at least three cannot be formed by just its single new edge. The explicit two-flip construction is optimal for the exception.
Watch out. Ignore diagonal entries. A connected color need not contain every edge. Do not greedily remove bridges. Return the actual flipped original vertex pairs, not merged supervertex indices. Distinguish an impossible target from one requiring zero operations.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<functional>
#include<iostream>
#include<limits>
#include<numeric>
#include<utility>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<vector<int>>color(n,vector<int>(n));
for(auto&row:color){
for(int&value:row){
cin>>value;
}
}
int red,blue;
cin>>red>>blue;
vector<pair<int,int>>answer;
auto components=[&](int wanted){
vector<int>component(n,-1);
int count=0;
function<void(int)>visit=[&](int u){
component[u]=count;
for(int v=0;v<n;++v){
if(u!=v&&color[u][v]==wanted&&component[v]==-1){
visit(v);
}
}
};
for(int u=0;u<n;++u){
if(component[u]==-1){
visit(u);
++count;
}
}
return component;
};
auto connected=[&](int wanted){
vector<int>c=components(wanted);
return *max_element(c.begin(),c.end())==0;
};
auto flip=[&](int u,int v){
color[u][v]^=1;
color[v][u]^=1;
answer.emplace_back(u+1,v+1);
};
if((!red&&!blue)||(red&&blue&&n==3)){
cout<<-1<<'\n';
return 0;
}
if(!red||!blue){
int wanted=red?1:0;
// Stoer-Wagner global minimum cut in the color that must be disconnected.
vector<vector<int>>weight(n,vector<int>(n));
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
weight[i][j]=(i!=j&&color[i][j]==wanted);
}
}
vector<int>active(n);
iota(active.begin(),active.end(),0);
vector<vector<int>>group(n);
for(int i=0;i<n;++i){
group[i].push_back(i);
}
int best=numeric_limits<int>::max();
vector<int>cut;
while(active.size()>1){
vector<int>strength(n),used(n);
int previous=-1;
for(size_t step=0;step<active.size();++step){
int vertex=-1;
for(int u:active){
if(!used[u]&&(vertex==-1||strength[u]>strength[vertex])){
vertex=u;
}
}
if(step+1==active.size()){
if(strength[vertex]<best){
best=strength[vertex];
cut=group[vertex];
}
for(int u:active){
if(u!=previous&&u!=vertex){
weight[previous][u]+=weight[vertex][u];
weight[u][previous]=weight[previous][u];
}
}
group[previous].insert(group[previous].end(),group[vertex].begin(),group[vertex].end());
active.erase(find(active.begin(),active.end(),vertex));
break;
}
used[vertex]=1;
previous=vertex;
for(int u:active){
if(!used[u]){
strength[u]+=weight[vertex][u];
}
}
}
}
vector<int>side(n);
for(int u:cut){
side[u]=1;
}
for(int u=0;u<n;++u){
for(int v=u+1;v<n;++v){
if(side[u]!=side[v]&&color[u][v]==wanted){
flip(u,v);
}
}
}
}
else if(!connected(0)||!connected(1)){
int missing=connected(0)?1:0;
vector<int>component=components(missing);
int count=*max_element(component.begin(),component.end())+1;
// Exceptional star: one flip connects the missing color but disconnects its complement.
int isolated=-1;
for(int u=0;u<n;++u){
int degree=0;
for(int v=0;v<n;++v){
degree+=(u!=v&&color[u][v]==missing);
}
if(degree==0){
isolated=u;
}
}
bool special=count==2&&isolated!=-1;
for(int u=0;u<n;++u){
for(int v=u+1;v<n;++v){
if(u!=isolated&&v!=isolated&&color[u][v]!=missing){
special=false;
}
}
}
if(special){
int a=(isolated+1)%n;
int b=(isolated+2)%n;
flip(isolated,a);
flip(a,b);
}
else{
while(!connected(missing)){
component=components(missing);
vector<int>entry(n,-1),low(n);
vector<vector<int>>bridge(n,vector<int>(n));
int timer=0;
function<void(int,int)>visit=[&](int u,int parent){
entry[u]=low[u]=timer++;
for(int v=0;v<n;++v){
if(u==v||color[u][v]==missing||v==parent){
continue;
}
if(entry[v]==-1){
visit(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>entry[u]){
bridge[u][v]=bridge[v][u]=1;
}
}
else{
low[u]=min(low[u],entry[v]);
}
}
};
visit(0,-1);
bool done=false;
for(int u=0;u<n&&!done;++u){
for(int v=u+1;v<n;++v){
if(component[u]!=component[v]&&!bridge[u][v]){
flip(u,v);
done=true;
break;
}
}
}
if(!done){
return 1;
}
}
}
}
cout<<answer.size()<<'\n';
for(auto edge:answer){
cout<<edge.first<<' '<<edge.second<<'\n';
}
}