Offline Dynamic Connectivity algorithm

오프라인 다이나믹 커넥티비티 알고리즘을 알아보자.

Offline Dynamic Connectivity 는 간선 추가, 삭제를 오프라인으로 처리하는 문제에 쓰인다.

대표적으로 BOJ의 16911 = 16912 = 15316 < 12876 < 15946 순으로 문제가 어렵다. (16911,16912,15316 이 3개중 하나만 풀어도 나머지 2개는 꽁짜..)

 

여러가지 방법이 있겠지만 저는 분할 정복을 사용했습니다. (사실 1가지임 ㅋ)

 

일단 간선의 라이프 타임을 저장해 둡니다. (나타난 시간 ~ 사라진 시간)

생기고 지워진 적이 없다면 맨 마지막 시간으로 해둡니다. (나타난 시간 ~ 마지막 시간)

 

이제 분할정복을 해줄텐데

 

solve(l,r,Edge set)

 

l~r : 간선 라이프 타임이 l~r 이고

m = (l + r) / 2 라고 하면

 

1. 간선들의 라이프 타임중 l~r 에 포함하는 간선을 Union-Find를 하든 뭘 하든 문제에 맞는 수행을 합니다.

2-1. 만약 l == r이면 l번째 질문 쿼리를 처리하고 롤백하고 return합니다.

2-2. 아니라면 l~m , m+1~r 의 두 구간으로 쪼개서 다시 분할정복을 합니다.

      l~m 로 함수를 호출할때 l~m을 포함하지 않는 간선은 버리고 함수를 호출합니다. (m+1~r 도 마찬가지 입니다.)

      식으로 나타내면 solve(l,m,Edge set - l~m을 포함하지 않는 간선), solve(m+1,r,Edge set - m+1~r을 포함하지 않는        간선) 으로 나타 낼 수 있습니다.

3. 아까 Union-Find를 하든 뭘 하든 문제에 맞는 수행 한것을 Rollback(되감기) 합니다.

 

이 방법을 수행하면 되는데 예를 들어보겠습니다.

1. A와 B사이의 간선을 추가한다.

2. A와 B사이의 간선을 삭제한다.

3. A와 B사이에 간선이 존재하면 1, 아니면 0을 출력한다.

 

이런 문제가 있습니다.

이런 경우는 Union-Find를 통해 합치고 없애는 방법을 사용합니다.

주로 쓰는 path compression 는 사용하지 않는다. Rollback할때 매우 꼬이기 때문이다. 그래서 대신 rank compression 를 사용합니다.
Rollback하는 것은 유니온 파인드로 합쳐질때마다 stack에 뭐가 합쳐졌는지 저장하고 나중에 저장한 만큼 pop하면서 이전 상태로 되돌리면 됩니다.

 

set을 직접 들고 다니면 O(Nlog^3N) 이지만 세그에 먼저 포함되는 구간을 다 박고 시작하면 O(Nlog^2N) 에 가능합니다.

 

그러면 코드를 보겠습니다. (16911 코드)

 

#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
int n,m,Q,cnt[100005],dep[100005],p[100005];
int vis[100005];
pii q[100005],QueryIn[100005];
map <pii,int> LifeTime;
vector <int> ans;
vector <pii> t[400005];
stack <pair<pii,int>> st;

struct LifeS {int x,y,s,e;};
vector <LifeS> life;

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

int merge(int x,int y) {
	x = Find(x), y = Find(y);
	if(x == y) return 0;
	if(dep[x] < dep[y]) swap(x,y);
	p[y] = x;
	if(dep[x] == dep[y]) {
		dep[x]++; st.push({{x,y},1});
	}
	else st.push({{x,y},0});
	return 1;
}

void add(int node,int l,int r,int rl,int rr,pii x) {
	if(l > rr||rl > r) return;
	if(rl <= l&&r <= rr) {
		t[node].push_back(x);
		return;
	}
	int mid = (l + r) >> 1;
	add(node*2,l,mid,rl,rr,x), add(node*2+1,mid+1,r,rl,rr,x);
}

void Rollback(int cntt) {
	for(int i = 1;i <= cntt;i++) {
		auto j = st.top(); st.pop();
		p[j.x.y] = j.x.y;
		if(j.y) dep[j.x.x]--;
	}
}

void query(int node,int l,int r) {
	int cntt = 0;
	for(auto i : t[node]) cntt += merge(i.x,i.y);
	if(l == r) {
		cout << (Find(q[l].x) == Find(q[l].y)) << '\n'; 
		Rollback(cntt);
		return;
	}
	int mid = (l + r) >> 1;
	query(node*2,l,mid); query(node*2+1,mid+1,r);
	Rollback(cntt);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> Q;
	for(int i = 1;i <= n;i++) p[i] = i,dep[i] = 0;
	for(int i = 1;i <= Q;i++) {
		int op,x,y;
		cin >> op >> x >> y;
		if(x > y) swap(x,y);
		if(op == 1) vis[i] = 1,LifeTime[{x,y}] = i,QueryIn[i] = {x,y};
		else if(op == 2) vis[LifeTime[{x,y}]] = 0,life.push_back({x,y,cnt[LifeTime[{x,y}]]+1,cnt[i-1]});
		else q[cnt[i-1]+1] = {x,y},cnt[i] = 1;
		cnt[i] += cnt[i-1];
	}
	for(int i = 1;i <= Q;i++) if(vis[i]) life.push_back({QueryIn[i].x,QueryIn[i].y,cnt[i]+1,cnt[Q]});
	for(LifeS i : life) add(1,1,cnt[Q],i.s,i.e,{i.x,i.y});
	query(1,1,cnt[Q]);
}