분할정복을 이용한 Offline Dynamic Connectivity Problem

https://koosaga.com/121

https://codeforces.com/gym/100551/problem/A

https://www.acmicpc.net/problem/16911

cp-algorithms.com/data_structures/deleting_in_log_n.html

 

1. 간선 추가

2. 간선 삭제

3. 정점 u, v가 연결되어 있는지 판별

 

이 문제를 online 으로 처리하는 것은 매우 어려운 문제이다. 따라서 Offline 으로 분할정복을 활용하여 해결하자.

 

가장 먼저, 각 간선의 생존시간을 시간축에 표시하면 어떠한 구간이 된다.

이 구간을 segment tree에 $logN$ 개의 노드에 업데이트 된 것이라고 생각하고, 이후 segment tree의 노드들을 전위순회하면서 union find 자료구조를 관리하자.

 

이때 주의해야 할 점은 union find 자료구조에서 roll back, 즉 마지막에 한 업데이트를 지우는 연산이 가능해야 한다. Union Find 에서 보통 쓰는 path compression 대신 rank optimization을 이용하자. 이를 이용하여 스택에 삭제해야 하는 간선들을 저장해 놓으면 $O(logN)$ 만에 삭제 가능한 union find를 구현할 수 있다.

 

이와 같은 방법은 단순히 이 상황에서만 사용되는 것이 아니라, 삽입, 복구가 가능한 자료구조에서 DNC와 비슷한 논리를 이용하여 단순 복구가 아닌 삭제가 가능하게 해준다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, M;
map<pii, int> MM;

pii A[MAXN+10];
vector<pii> tree[MAXN*4+10];

void update(int node, int tl, int tr, int l, int r, pii v)
{
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r) { tree[node].push_back(v); return; }
	int mid=tl+tr>>1;
	update(node*2, tl, mid, l, r, v);
	update(node*2+1, mid+1, tr, l, r, v);
}

int par[MAXN+10], sz[MAXN+10];
vector<int> S;

int Find(int x)
{
	if(x==par[x]) return x;
	return Find(par[x]);
}

void Union(int x, int y)
{
	x=Find(x); y=Find(y);
	if(sz[x]<sz[y]) swap(x, y);
	par[y]=x; sz[x]+=sz[y];
	S.push_back(y);
}

void restore()
{
	int t=S.back();
	sz[par[t]]-=sz[t]; par[t]=t;
	S.pop_back();
}

void dfs(int node, int tl, int tr)
{
	int cnt=0;
	for(auto it : tree[node]) if(Find(it.first)!=Find(it.second)) Union(it.first, it.second), cnt++;
	if(tl==tr)
	{
		if(A[tl].first) printf("%d\n", Find(A[tl].first)==Find(A[tl].second));
		while(cnt--) restore();
		return;
	}
	int mid=tl+tr>>1;
	dfs(node*2, tl, mid);
	dfs(node*2+1, mid+1, tr);
	while(cnt--) restore();
}

int main()
{
	int i, j;
	scanf("%d%d", &N, &M);
	for(i=1; i<=M; i++)
	{
		int t, u, v;
		scanf("%d%d%d", &t, &u, &v);
		if(u>v) swap(u, v);
		if(t==1) MM[{u, v}]=i;
		else if(t==2) update(1, 1, M, MM[{u, v}], i, {u, v}), MM.erase({u, v});
		else A[i]={u, v};
	}
	for(auto it : MM) update(1, 1, M, it.second, M, it.first);

	for(i=1; i<=N; i++) par[i]=i, sz[i]=1;
	dfs(1, 1, M);
}