When Bipartiteness Breaks
National Olympiad — Municipal round (2025 season)
Submission name: bipartite.cpp
Problem summary
Check whether an initial undirected graph is bipartite. If it is not, print −1. Otherwise add q edges in the given order and report the one-based index of the first edge that destroys bipartiteness. Print −2 if every addition preserves it. Loops and parallel edges are allowed.
Source clarification. The printed lower bounds say m,q ≥ 1, but official examples and a subtask explicitly use zero. The implementation accepts these documented cases.
Input
n m q, then m initial edges, then q additional edges in insertion order.
Output
−1, −2, or the first failing insertion index.
Constraints
1 ≤ n ≤ 2·10⁵; 0 ≤ m,q ≤ 4·10⁵; endpoints in [1,n]. Examples and subtasks allow m=0 and q=0.
Worked example
An independently prepared example for this explanation.
Input
3 0 3 1 2 1 3 2 3
Output
3
Solution analysis
- Maintain a disjoint-set union with a parity bit on every parent link. The parity of a vertex relative to its component root describes its color up to flipping the entire component. Path compression must XOR the old link parity with the parity of its old parent to the root.
- An edge u−v requires opposite colors. If the roots agree, the edge is consistent exactly when parity(u) XOR parity(v) is 1. If the roots differ, merge the components and choose the new root-link parity so this equation holds; union by size keeps the structure shallow.
- Process initial edges first and remember any contradiction. Then scan added edges, retaining only the first contradiction if the initial graph was valid. For the triangle example, edges 1−2 and 1−3 make vertices 2 and 3 have equal color; adding 2−3 is therefore the first contradiction, at index 3.
Why it works
The DSU invariant states that link parities encode all previously consistent opposite-color constraints in each component. A merge can always satisfy a new intercomponent constraint by flipping one component, and the formula installs exactly that flip. A same-component edge is possible if and only if its already determined endpoint parity is one. Thus a rejected edge is exactly an edge that makes a bipartite coloring impossible. Processing in order yields the required first index.
Watch out. A self-loop contradicts immediately; repeated ordinary edges need not. Check the initial graph separately. Preserve parity during path compression.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<numeric>
#include<utility>
#include<vector>
using namespace std;
class ParityDSU{
vector<int>parent,size,parity;
public:
explicit ParityDSU(int n):parent(n+1),size(n+1,1),parity(n+1,0){
iota(parent.begin(),parent.end(),0);
}
pair<int,int>find(int vertex){
if(parent[vertex]==vertex){
return {vertex,0};
}
auto result=find(parent[vertex]);
parity[vertex]^=result.second;
parent[vertex]=result.first;
return {parent[vertex],parity[vertex]};
}
bool add(int u,int v){
auto a=find(u);
auto b=find(v);
if(a.first==b.first){
return (a.second^b.second)==1;
}
if(size[a.first]<size[b.first]){
swap(a,b);
}
parent[b.first]=a.first;
// Enforce color(u) XOR color(v) = 1 across the new root link.
parity[b.first]=a.second^b.second^1;
size[a.first]+=size[b.first];
return true;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,q;
cin>>n>>m>>q;
ParityDSU dsu(n);
int answer=-2;
for(int i=0;i<m+q;++i){
int u,v;
cin>>u>>v;
if(!dsu.add(u,v)&&answer==-2){
answer=i<m?-1:i-m+1;
}
}
cout<<answer<<'\n';
}