오프라인 동적 연결성

간선 수명을 세그 트리에 올려 롤백 DSU로.

다이아몬드 III

1강 간선 수명을 세그 트리에 올리기 공식

문제

간선이 시간에 따라 추가되고 삭제되며, 중간중간 "현재 연결 요소 수" 또는 "두 정점이 연결됐는가" 를 묻는다. 추가만 있으면 DSU로 충분하지만 삭제가 있으면 DSU는 효율적으로 되돌릴 수 없다. 오프라인이 허용되면 시간축 세그먼트 트리 + 롤백 DSU 로 $O((n+q)\log q\,\alpha)$ 에 푼다.

핵심 아이디어

각 간선은 어떤 시간 구간 $[t_{add}, t_{del})$ 동안만 존재한다. 이 수명 구간을 시간축 세그먼트 트리에 표준 분해 로 $O(\log q)$ 개의 노드에 매단다. 그러면 세그 트리를 DFS로 순회하면서:

노드에 진입할 때 그 노드에 매달린 간선들을 DSU에 union,
리프(=특정 시각)에 도달하면 그 시각의 질의를 현재 DSU 상태로 답하고,
노드에서 나올 때 진입 시 했던 union을 롤백.

각 간선은 $O(\log q)$ 개 노드에 들어가고, 각 노드 방문에서 union/rollback 한 번이므로 전체 $O((n+q)\log q\,\alpha)$ . ( $\alpha$ 는 경로 압축 없는 union-by-rank의 역아커만, 실질 상수.)

롤백 DSU

경로 압축은 되돌리기 어렵다. 그래서 union-by-rank만 쓰고 경로 압축을 포기한다(높이 $O(\log n)$ 유지). union이 바꾼 부모/랭크를 스택에 기록해 두고, 롤백 시 역순으로 복원한다. 따라서 find 는 $O(\log n)$ , union/rollback은 $O(\log n)$ .

정확성

세그 트리 DFS가 리프 $$t$$ 에 도달했을 때 DSU에 들어 있는 간선은 정확히 "수명 구간이 $$t$$ 를 포함하는 간선들" 이다. 표준 구간 분해의 성질상, 루트→리프 경로 위 노드들에 매달린 간선의 합집합이 그 시각 활성 간선이기 때문이다.

비교

상황	도구
추가만	DSU
추가+삭제, 오프라인	시간 세그 트리 + 롤백 DSU
추가+삭제, 온라인	링크-컷 트리 / 유클리드 트릭(어려움)

2강 구현: 시간 세그 트리 + 롤백 DSU 공식

전체 골격

연결 요소 수를 시각별로 출력하는 예. 같은 간선의 추가/삭제 쌍을 매칭해 수명 구간을 만든다.

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

struct RollbackDSU {
    vector<int> p, r; int comps;
    vector<array<int,3>> hist;                 // {child, rankBumped, ...}
    void init(int n){ p.resize(n); r.assign(n,0); iota(p.begin(),p.end(),0); comps=n; }
    int find(int x){ while(x!=p[x]) x=p[x]; return x; }   // 경로 압축 없음
    void uni(int a,int b){
        a=find(a); b=find(b);
        if(a==b){ hist.push_back({-1,0,0}); return; }      // no-op도 기록
        if(r[a]<r[b]) swap(a,b);
        hist.push_back({b, (r[a]==r[b])?1:0, 0});
        p[b]=a; if(r[a]==r[b]) r[a]++; comps--;
    }
    void rollback(){
        auto e=hist.back(); hist.pop_back();
        if(e[0]==-1) return;
        int b=e[0]; r[p[b]]-=e[1]; p[b]=b; comps++;
    }
};

int Q;                                         // 시각 수(질의 시점)
vector<vector<pair<int,int>>> segEdges;        // 세그 노드별 매달린 간선
RollbackDSU dsu;
vector<int> answer;

void addEdge(int node,int l,int r,int ql,int qr,pair<int,int> e){
    if(qr<l||r<ql) return;
    if(ql<=l&&r<=qr){ segEdges[node].push_back(e); return; }
    int m=(l+r)/2;
    addEdge(node*2,l,m,ql,qr,e);
    addEdge(node*2+1,m+1,r,ql,qr,e);
}
void dfs(int node,int l,int r){
    for(auto& e:segEdges[node]) dsu.uni(e.first,e.second);   // 진입: union
    if(l==r) answer[l]=dsu.comps;                            // 리프: 질의 응답
    else { int m=(l+r)/2; dfs(node*2,l,m); dfs(node*2+1,m+1,r); }
    for(size_t i=0;i<segEdges[node].size();i++) dsu.rollback(); // 퇴장: 롤백
}

자주 하는 실수

경로 압축 사용. 롤백이 불가능해진다. 반드시 union-by-rank만.
no-op union 미기록. 같은 집합 union도 hist 에 더미를 push해야 롤백 횟수가 맞는다.
수명 구간 경계. 삭제 시점이 $t_{del}$ 이면 간선은 $[t_{add}, t_{del}-1]$ 에 존재. off-by-one을 점검한다.
끝까지 안 지워지는 간선. $t_{del}$ 을 $$Q-1$$ (마지막 시각)로 둔다.
롤백 순서. 진입에서 한 union 횟수만큼 퇴장에서 역순 롤백.

응용

문제	질의
동적 연결 요소 수	`comps`
두 정점 연결 여부(시각별)	`find(u)==find(v)`
이분 그래프 유지	가중 DSU(패리티) + 롤백
MST 변형(시간 구간 간선)	롤백 + 정렬

변형

질의가 "두 정점 연결?" 이면 리프에서 그 질의만 답한다. 이분성 판정은 패리티 가중 DSU를 롤백 가능하게 만들면 된다. 온라인이 필요하면 링크-컷 트리로 넘어간다.