Problem 56: Offline Dynamic Connectivity
Problem Statement: Given an undirected graph with n nodes and q queries of two types (add edge and remove edge) and connectivity queries, answer all connectivity queries offline.
Input
The first line contains n and q. Each of the next q lines starts with a type: 1 u v (add edge), 2 u v (remove edge), or 3 u v (check if u and v are connected). Initially, the graph is empty.
Output
For each query of type 3, print "YES" if u and v are connected by the current set of edges, otherwise print "NO".
Examples
Input:
5 6
1 1 2
1 2 3
3 1 3
2 1 2
3 1 3
3 4 5
Output:
YES
NO
NO
Solution Explanation
This problem is solved using offline processing with a union-find data structure in combination with a segment tree or divide and conquer technique to simulate the lifetime of edges. Each edge addition and removal is processed in segments and connectivity queries are answered using union-find snapshots.
Solution in C++
#include
#include
using namespace std;
struct DSU {
vector parent, size;
vector> history;
int comp;
DSU(int n): parent(n+1), size(n+1, 1), comp(n) {
for (int i = 0; i <= n; i++)
parent[i] = i;
}
int find(int a) { return parent[a] == a ? a : find(parent[a]); }
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
if (size[a] < size[b]) swap(a, b);
history.push_back({b, parent[b]});
parent[b] = a;
size[a] += size[b];
comp--;
return true;
}
void rollback(int checkpoint) {
while(history.size() > checkpoint) {
auto x = history.back();
history.pop_back();
int b = x.first;
int par = x.second;
size[parent[b]] -= size[b];
parent[b] = par;
comp++;
}
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}