Offline Dynamic Connectivity - 오프라인 동적 연결성 판정

들어가기 전에, 코드는 파이썬으로 작성했으니 참고했으면 좋겠다. 어자피 작동 원리는 같으니 문제는 안 된다.

 

 

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

16911번: 그래프와 쿼리

이 문제를 풀어보자. 처음에는 어떤 두 정점도 연결되지 않은 상태이고, 다음 쿼리들을 수행하는 문제이다.

1번 쿼리: 두 정점을 연결하는 간선을 추가한다.

2번 쿼리: 두 정점을 연결하는 간선을 제거한다.

3번 쿼리: 정점 u에서 v로 가는 경로의 존재 여부를 출력한다.

 

2번 쿼리가 없다면, 단순하게 union-find로 풀 수 있을 것이다. 그러나, 이 문제는 그렇지 않으므로 어떤 방법을 생각해야 할 것 같다.

 

먼저, 간선의 연대표를 만들자. 시간의 기준은 3번 쿼리이다.

이제 이것을 이용해서 분할 정복을 할 것이다. 간선이 구간 \([s, e]\)을 포함하면 union해준다. 아니라면, 세그먼트 트리에서 구간을 나누는 것처럼 양쪽으로 재귀적으로 내려가자. \(s==e\)일 때 s번째 쿼리를 처리해주면 된다.

def divide(x, s, e):
    cnt = 0
    for go in seg[x]:
        cnt += union(find(go[0]), find(go[1]))
 
    if s == e:
        print(int(find(query[s][0]) == find(query[e][1])))
       undo(cnt)
        return
 
    mid = (s + e) // 2
    divide(x * 2, s, mid)
    divide(x * 2 + 1, mid + 1, e)
   undo(cnt)

go는 간선 (u, v)이다. undo 함수는 바로 아래 문단에서 다룬다.

 

쿼리를 처리해준 후, union해준 간선을 되돌려야 한다. 그러나 문제가 있다. 흔한 union-find 방법인 path-compression를 사용한다면, 되돌리는 과정이 매우 비효율적일 것이다. 이를 해결하기 위해서, rank-compression을 사용할 것이다. Rank-compression은 정말 간단하다. 높이가 낮은 트리를 높은 트리에 합치는 union 과정을 거치면 된다.

(높이가 같은 두 트리를 합칠 때는 높이가 1 증가하므로, rank 또한 1 증가한다.)

 

이를 이용한다면, undo를 매우 편하게 할 수 있다.

def find(x):
    if x == p[x]:
        return x
    return find(p[x])
 
 
def union(x, y):
    if x == y:
        return 0
    if rank[x] < rank[y]:
        x, y = y, x
    p[y] = x
 
    if rank[x] == rank[y]:
        rank[x] += 1
        st.append([x, y, 1])
    else:
        st.append([x, y, 0])
    return 1
 
 
def undo(cnt):
    for i in range(cnt):
        now = st.pop()
        p[now[1]] = now[1]
        if now[2]:
            rank[now[0]] -= 1

find, union, undo 함수이다. find는 설명을 생략하고, union에서는 rank가 증가하는 경우를 따로 처리해주면 된다. 스택을 이용하여, undo할 때 pop하면서 되돌리면 된다. 높이가 낮은 트리의 루트의 부모 정보를 원래대로 되돌리기만 하면 된다.

 

 

map을 활용하여 간선의 lifetime을 저장할 수 있다. 아래에 전체코드를 첨부하겠다.

import sys
input = sys.stdin.readline
 
 
def ip(): return int(input())
 
def mip(): return map(int, input().split())
 
def lmip(): return list(map(int, input().split()))
 
 
def find(x):
    if x == p[x]:
        return x
    return find(p[x])
 
 
def union(x, y):
    if x == y:
        return 0
    if rank[x] < rank[y]:
        x, y = y, x
    p[y] = x
 
    if rank[x] == rank[y]:
        rank[x] += 1
        st.append([x, y, 1])
    else:
        st.append([x, y, 0])
    return 1
 
 
class Node:
    def __init__(self, u, v, s, e):
        self.u = u
        self.v = v
        self.s = s
        self.e = e
 
 
p = [i for i in range(101010)]
time = [Node(0, 0, 0, 0) for _ in range(202020)]
seg = [[] for _ in range(808080)]
rank = [0 for _ in range(101010)]
edge = []
query = [[0, 0] for _ in range(202020)]
mp = dict()
c = 0
st = []
 
 
def update(x, s, e, l, r, go):
    if r < s or e < l:
        return
    if l <= s and e <= r:
        seg[x].append(go)
        return
    mid = (s + e) // 2
    update(x * 2, s, mid, l, r, go)
    update(x * 2 + 1, mid + 1, e, l, r, go)
 
 
def divide(x, s, e):
    cnt = 0
    for go in seg[x]:
        cnt += union(find(go[0]), find(go[1]))
 
    if s == e:
        print(int(find(query[s][0]) == find(query[e][1])))
       undo(cnt)
        return
 
    mid = (s + e) // 2
    divide(x * 2, s, mid)
    divide(x * 2 + 1, mid + 1, e)
   undo(cnt)
 
 
def undo(cnt):
    for i in range(cnt):
        now = st.pop()
        p[now[1]] = now[1]
        if now[2]:
            rank[now[0]] -= 1
 
 
n, m = mip()
 
for i in range(1, m + 1):
    op, a, b = mip()
    if a > b:
        a, b = b, a
 
    if op == 1:
        mp[str(a) + " " + str(b)] = i
        time[i] = Node(a, b, c + 1, -1)
    elif op == 2:
        j = mp[str(a) + " " + str(b)]
        time[j].e = c
        edge.append(time[j])
    else:
        c += 1
        query[c] = [a, b]
 
for i in range(1, m + 1):
    if time[i].e == -1:
        time[i].e = c
        edge.append(time[i])
 
for e in edge:
    update(1, 1, c, e.s, e.e, [e.u, e.v])
 
divide(1, 1, c)
 
 
######## Praise greedev ########

빠르게(?) 작동한다.

 

 

[연습 문제들]

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

=16911.

 

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

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

 

 

아래 두 문제는 아직 안 풀었다.ㅎ

푸는대로 풀이를 추가하도록 하겠따