Offline dynamic Connectivity

오프라인 다이나믹 커넥티비티 (offline dynamic connectivity)

1년전에 배우고 최근에 복습한 알고리즘. 이번 글에서는 오프라인 다이나믹 커넥티비티라는 알고리즘에 대해서 다뤄보려고 한다. 이 글에서 앞으로 odc 라고 줄여쓰기도 할 것 같다. 

When?

어떤 문제를 풀기 위해 쓰느냐. life가 있는 변화들과 질문들이 쿼리로 들어왔을 때 사용한다. 
문제 www.acmicpc.net/problem/16911를 보자. 각 간선들은 연결을 했다가 일정 시점 이후 사라진다. 또한, 중간에 어떤 두 점의 연결성을 물어보는 쿼리들이 주어진다. 이런 형태의 변화되는 선분과 두 점간의 연결성을 물어보는 문제가 대표적인 odc를 쓰는 문제이다. 위에서 소개한 문제를 odc로 푸는 과정을 소개할 예정이다.

Previous Algorithm

이 알고리즘을 이해하기 위해서는 Segment Tree에 대한 기본적인 이해가 필요하다. 물론 위에 소개한 기초 odc 문제를 풀기 위해서는 Union & Find 에 대한 지식도 있어야 한다. 

How?

이제 어떻게 동작하는지에 대해서 말해보려고 한다. 모든 동작은 하나의 세그트리에서 이루어지게 된다. 전체적인 매커니즘은 쿼리들을 세그트리에 표지해 놓은다음에 세그트리에서 dfs를 돌면서 표지해 놓은 쿼리들을 순서대로 진행하면 된다. 

선분은 lazy propagation을 하지 않는 구간 업데이트라고 생각하면 된다. life를 구간별로 쪼개서 구간에 해당하는 노드에 저장을 해놓으면 된다. 

void uptl(pii ed,ll l,ll r,ll s,ll e,ll nod){
	if(r<s||e<l) return;
	if(l<=s&&e<=r){
		tree[nod].eds.pb(ed);
		return;
	}
	uptl(ed,l,r,s,(s+e)/2,nod*2);
	uptl(ed,l,r,(s+e)/2+1,e,nod*2+1);
}

위의 코드는 life가 있는 선분을 세그에 담는 코드이다. ed가 선분이고, eds가 노드에서 선분을 담아둘 벡터이다. 세그트리를 좀 짜봤다면 익숙할 것이라고 생각한다.

질문 쿼리를 어떻게 처리할지는 사람마다 다르고, 개인 취향차이이다. 나는 보통 세그트리에다가 질문 쿼리도 박아버리는 편이다. 해당 위치의 리프노드에 질문으로 들어온 두개의 점의 번호를 저장해 놓는다.

void chk(ll idx,ll pp1,ll pp2,ll s,ll e,ll nod){
	if(idx<s||idx>e) return ;
	if(s==e){
		tree[nod].sol=1;
		tree[nod].p1=pp1;
		tree[nod].p2=pp2;
		return ;
	}
	chk(idx,pp1,pp2,s,(s+e)/2,nod*2);
	chk(idx,pp1,pp2,(s+e)/2+1,e,nod*2+1);
}

 두 개의 점 pp1,pp2를 해당 위치인 idx에 저장했다. 나중에 dfs를 도는 과정에서 리프노드에서 노드의 sol값이 1이라면 쿼리를 처리해 주면 될 것이다.

 이런식으로 세그트리의 노드들에 다 표지해 놓았으면 그냥 세그트리를 순서대로 돌면서 쿼리들을 처리해주면 된다. 노드에 들어가면서 eds에 있는 선분들에 대해서 union을 해주고, 들어간 노드가 리프 노드면서 sol이 1인 상황에서 전체적인 상태를 보면 life 구간에 s가 포함되어 있는 선분들에 대한 merge 들만 진행된 상태일 것이다. 따라서 두 점이 같은 그룹에 있는지에 대해서 확인하면 쿼리에 대한 답을 알 수 있다. . 

여기서 핵심은 어떤 노드에 대해서 eds에 선분이 있다면 나올 때 그 선분들에 해당하는 union 과정들을 뒤로 돌리는 것이다.

void dfs(ll s,ll e,ll nod){
	ll sz=tree[nod].eds.size();
	for(ll i=sz-1;i>=0;i--){
		auto k=tree[nod].eds[i];
		uni(k.ff,k.ss);
	}
	if(s==e){
		if(tree[nod].sol){
			if(fi(tree[nod].p1)==fi(tree[nod].p2)) ans[s]=1;
			else ans[s]=0;
		}
		for(auto k:tree[nod].eds){
			undo();
		}
		return ;
	}
	dfs(s,(s+e)/2,nod*2);
	dfs((s+e)/2+1,e,nod*2+1);
	for(auto k:tree[nod].eds){
		undo();
	}
	return ;
}

 여기서 undo 함수로 해놓은 부분이 선분에 대해서 union을 뒤로 되돌리는 과정이다. 이 문제에 대해서는 선분으로 인한 union을 되돌리는 과정이지만, odc가 어떻게 응용되는 지에 따라서 다른 쿼리가 들어올 수 있고, 그 쿼리를 그 전으로 되돌리는 과정이 undo가 될 것이다. 
 이를 바꿔서 생각하면 어떤 life가 존재하는 변화쿼리가 이 전으로 되돌릴 수 있는 즉, undo가 가능한 쿼리일 때 odc를 쓸 수 있는 조건이 되는 것이다. 
 따라서 이 문제에 대한 odc를 할 때에는 union & find를 할때  par[a] = fi(par[a]) 을 통해 실시간으로 부모를 업데이트 해주는 경로압축을 쓰면 안된다. 경로압축을 하는 union & find는 undo를 할 수 없다. 

전체적인 시간복잡도는 N개의 쿼리가 life가 lgN개로 쪼개지고 u&f 에 lgN의 시간 복잡도가 걸리기 때문에 총 시간복잡도는 $O(Nlg^2N)$ 이 걸리게 된다. 

Why?

어떤 매커니즘으로 이 알고리즘이 진행되는지 알았으니, 이제 왜 이 알고리즘을 써야되는지, 왜 이런식으로 해야 하는지에 대해서 말해보려고 한다. 

두 개의 선분 쿼리가 주어진다고 생각하자. 시간 구간은 1부터 8까지 있고, 두개의 쿼리중 쿼리 a는 시간 1~5, 나머지 쿼리 b는 시간 3~8동안 진행된다고 가정하자. 가장 먼저 생각할 수 있는 방법은 시간 순서대로 진행하는 것이다. 시점 1에서 a를 처리하고 시점 3에서 b처리하고 5에서 a'을 처리하고 8에서 b'을 처리한다. 
즉 처리 순서가 a->b->a'->b'이 되는데 뒤로 되돌리는 방법이 가장 최근에 처리한 변화만을 되돌릴 수 밖에 없는 것이다. 하지만 이를 세그트리에서 쪼개서 처리한다면 a를 1~4,5~5로, b를 3~4,5~8로 쪼갤 수 있고, 순서는 
a(1~4)->b(3~4)->b'(3~4)->a'(1~4)->b(5~8)->a(5~5)->a'(5~5)->b'(5~8) 가 된다.
즉, 모든 undo 과정이 내가 처리한 쿼리들의 역순으로 진행한다는 것이 핵심이다. 

Code

문제를 푼 소스코드이다.

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define mp make_pair
 
ll par[101010];
ll siz[101010];
pii stac[1010101];
ll ccnt;
void init(ll x){
    for(ll i=1;i<=x;i++)
        par[i]=i;
}
ll fi(ll x){
    while(par[x]!=x) x=par[x];
    return x;
}
void uni(ll a,ll b){
    a=fi(a);
    b=fi(b);
    ccnt++;
    if(a==b){
        stac[ccnt]={0,0};
        return;
    }
    if(siz[a]>siz[b]) swap(a,b);
    par[a]=b;
    stac[ccnt]={a,b};
    if(siz[a]==siz[b]) siz[b]++;
}
void undo(){
    ll a=stac[ccnt].ff;
    ll b=stac[ccnt].ss;
     ccnt--;
    if(a+b==0) return;
    par[a]=a;
    if(siz[b]==siz[a]+1) siz[b]--;
}
 
ll ans[1010101];
struct node{
    vector<pii> eds;
    ll sol,p1,p2;
};
node tree[404040];
 
void uptl(pii ed,ll l,ll r,ll s,ll e,ll nod){
    if(r<s||e<l) return;
    if(l<=s&&e<=r){
        tree[nod].eds.pb(ed);
        return;
    }
    uptl(ed,l,r,s,(s+e)/2,nod*2);
    uptl(ed,l,r,(s+e)/2+1,e,nod*2+1);
}
 
void chk(ll idx,ll pp1,ll pp2,ll s,ll e,ll nod){
    if(idx<s||idx>e) return ;
    if(s==e){
        tree[nod].sol=1;
        tree[nod].p1=pp1;
        tree[nod].p2=pp2;
        return ;
    }
    chk(idx,pp1,pp2,s,(s+e)/2,nod*2);
    chk(idx,pp1,pp2,(s+e)/2+1,e,nod*2+1);
}
 
void dfs(ll s,ll e,ll nod){
    ll sz=tree[nod].eds.size();
    for(ll i=sz-1;i>=0;i--){
        auto k=tree[nod].eds[i];
        uni(k.ff,k.ss);
    }
    if(s==e){
        if(tree[nod].sol){
            if(fi(tree[nod].p1)==fi(tree[nod].p2)) ans[s]=1;
            else ans[s]=0;
        }
        for(auto k:tree[nod].eds){
            undo();
        }
        return ;
    }
    dfs(s,(s+e)/2,nod*2);
    dfs((s+e)/2+1,e,nod*2+1);
    for(auto k:tree[nod].eds){
        undo();
    }
    return ;
}
 
 
 
vector<pii> v[1010101];
 
int main()
{
    ll i,j,k,l,m,n,a,b,c;
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=m;i++){
        ans[i]=-1;
        scanf("%lld %lld %lld",&a,&b,&c);
        if(a==1||a==2){
            if(b<c) swap(b,c);
            v[b].eb(c,i);
        }
        else{
            chk(i,b,c,1,m,1);
        }
    }
    init(n);
    for(i=1;i<=n;i++){
        sort(v[i].begin(), v[i].end());
        ll sz=v[i].size();
        for(j=0;j<sz;j++){
            if(j==sz-1||v[i][j].ff!=v[i][j+1].ff){
                uptl(mp(i,v[i][j].ff),v[i][j].ss,m,1,m,1);
            }
            else{
                uptl(mp(i,v[i][j].ff),v[i][j].ss,v[i][j+1].ss,1,m,1);
                j++;
            }
            
        }
    }
    dfs(1,m,1);
    for(i=1;i<=m;i++){
        if(ans[i]!=-1)
            printf("%lld\n",ans[i]);
    }
 
}