테페리넷

사용자 도구

사이트 도구

현재 위치: 테페리넷 » Problem Solving » 동적 연결성
ps:동적_연결성

목차

동적 연결성

  • 개념은 Dynamic Connectivity를 참고하자.
  • 몇가지 케이스로 분류할 수 있고, 문제의 난이도도 이에 따라 달라진다
    • 쿼리 종류에 따라서 '엣지를 추가하는 쿼리만 들어올 때' / '엣지를 삭제하는 쿼리만 들어올 때' / '두 종류의 쿼리가 모두 들어올 때' 로 분류
    • 그래프 종류에 따라서 '트리' / '일반 그래프' 로 분류
    • '오프라인 쿼리로 처리 가능한 경우' / '오프라인 쿼리로 처리가 불가능한 경우' 로 분류
  • 이 중에서 쉽게 풀이가 가능한 경우들은
    • 엣지를 추가하는 쿼리만 들어올 때 → 가장 쉽다. Disjoint Set으로 해결 가능.
    • 오프라인 쿼리로 처리 가능하고 엣지를 삭제하는 쿼리만 들어올때. → 역순으로 업데이트해나가면 엣지를 추가하는 쿼리만 들어오는 경우랑 동일해짐
    • 트리일 때 → 문제에 따라 다양한 방법이 존재. Link-Cut tree 등으로 해결 가능
    • 오프라인 쿼리로 처리 가능한 경우 → '오프라인 동적 연결성'이라고 불리는 문제. 분할 정복과 롤백을 지원하는 Disjoint Set을 함께 사용하는 방법이 있다
    • 다 안될때… 추가 삭제가 다 있는데, 트리도 아니고, 오프라인 처리도 안된다 → 온라인 동적 연결성 체크를 해야 한다

엣지를 추가하는 쿼리만 들어올 때

  • 그냥 Disjoint set으로 관리해주면 끝이다. 연결성 확인과 엣지 추가를 O(α(n))에 처리할 수 있다.
  • 사실 이 자체로는 설명할게 없고.. (풀이는 전혀 다르지만) 비슷한 느낌의 문제를 여기 같이 언급한다.

엣지가 추가되는 도중에, 두 노드가 처음 연결되는 시점을 묻는 문제

  • 연결성을 확인할 노드쌍이 한개만 주어진다면, Disjoint set으로 엣지를 추가할때마다 연결여부를 확인해보면 된다.
  • 문제는 연결성을 확인할 노드쌍이 Q개의 쿼리로 주어지는 경우이다.
  • 크게 3가지 방법이 있다.
    • 추가시키는 엣지들로 트리를 '잘' 만들고, 쿼리들을 트리에서의 LCA나 경로최댓값으로 처리하는 방법이다. 쿼리들을 온라인으로 처리 가능
    • 오프라인 쿼리가 가능할때에는 쿼리들을 small-to-large 테크닉으로 관리하며 풀 수 있다. 컴포넌트마다 대응되는 쿼리들을 유지하고, 컴포넌트가 합쳐질때마다 해당되는 쿼리들을 해결하는 방법이다.
    • 역시 오프라인 쿼리가 가능할때에는 병렬 이분 탐색 (Parallel Binary Search; PBS)을 써서도 풀 수 있다.
  • 어째서인지 이런 유형은 PBS의 전형적인 유형이라고 설명된다. BOJ에서 PBS태그가 달린 문제들중 거의 절반이 이 문제의 변형이다. 근데 앞에서 말한 세가지 방법중 보통은 PBS가 제일 느리다..
  • 1396 문제를 기준으로 걸린 시간은 다음과 같았다 (python 3.11기준)
  • 라이브러리 부분을 제외하고, 직접 짜야하는 코드가 가장 짧은것은 PBS이긴 하지만, small-to-large도 코드짜기가 어렵지는 않다.

온라인/트리/경로쿼리

  • 엣지들을 추가할때, 이미 연결된 노드들간에는 엣지를 추가하지 않아도 되므로, 결국은 트리가 만들어진다.
  • 엣지를 추가할때, 현재 시점 t를 추가한 엣지의 가중치로 주자.
  • 그러면 x와 y가 연결된 시점은, x-y사이의 경로의 엣지중에서 가장 가중치가 큰 것이 된다.
  • 경로 최댓값 쿼리이고, 업데이트가 없으니까, binary lifting 을 써서 처리하면 된다.
  • E개의 엣지를 dsu로 추가하면서, 트리를 만드는데에 O(E*α(V))가 걸린다. 트리에서 경로최댓값쿼리를 위한 테이블을 만드는데에 O(VlogV)가 걸리고 Q개 쿼리를 처리하는 것은 O(QlogV)가 걸린다.
  • 총 시간복잡도는 O(E*α(V) + (Q+V)logV)이다

온라인/트리/LCA

  • 엣지들을 추가하면서 트리를 만드는 것은 비슷하다.
  • 현재 시점을 엣지의 가중치로 저장하는게 아니라, 노드에 매핑시켜서 저장한다. 그리고 그 노드가 지금 합쳐진 컴포넌트들의 LCA가 되도록 트리를 만드는 것이다.
  • 처음에 컴포넌트들이 각각의 트리로 표현될때, 루트 노드를 기억하고있는다. x와 y를 합친다면, x와 y에 엣지를 연결하는 것이 아니라, x가 속한 컴포넌트의 루트노드와 y가 속한 컴포넌트의 루트노드를 연결해주게 된다. 이것도 그대로 연결하는 것이 아니라.. 새로운 노드를 하나 추가해서 그 노드가 x의 루트노드와 y의 루트노드의 공통 부모가 되게 한다. 이러면 새 노드는 합쳐진 컴포넌트의 루트노드가 된다. 그리고 그 노드에 현재 시점을 매핑시켜 저장한다
  • 이렇게 트리를 다 만들고 나면, x와 y가 연결된 시점은 x와 y의 LCA노드에 매핑된 값이 된다.
  • E개의 엣지를 dsu로 추가하면서, 트리를 만드는데에 O(E*α(V))가 걸리는 것은 동일하다. 트리에서 LCA 쿼리를 처리하는 것은 HLD를 사용했을때 구축에 O(V), Q개 쿼리를 처리하는 것에 O(QlogV)가 걸린다. LCA 쿼리 처리를 RMQ로 변환해서 Sparse table을 써서 한다면, 구축에 O(VlogV), Q개쿼리 처리에 O(Q)가 된다. 보통 Q와 V가 비슷하면 전자의 방법이 더 빠르다
  • 암튼 총 시간 복잡도는 O(E*α(V) + V + QlogV) 또는 O(E*α(V) + Q + VlogV) 이다
  • 만들어진 트리가 실제로는 2*V개의 노드를 갖게 되지만, 그래도 경로쿼리 방법보다 빨리 돌아간다.
  • 문제에 따라서 노드에 가중치를 바로 줄수 있게 되어있는 문제들이 있다. 이경우는 그냥 V개의 노드를 갖는 트리로 만들수 있고 코드도 간단해진다.

오프라인/small-to-large

  • 각 컴포넌트마다, 이 컴포넌트의 원소를 포함하는 쿼리의 번호들을 갖고 있도록 한다.
  • 한 쿼리는 두개의 노드를 포함하므로, 동일한 번호를 갖는 컴포넌트는 두개이다
  • 컴포넌트가 합쳐질때마다, 두 컴포넌트의 쿼리번호집합을 합치게 된다.
  • 합치는 과정에서 동일한 쿼리번호가 양쪽 집합에 있었다면, 현재 시점이 그 쿼리의 해답이 된다.
  • 두개의 쿼리번호 집합을 합치는 것을 small-to-large 방식으로 처리하면, 모든 쿼리번호집합이 합쳐질때까지 O(QlogQ)번의 연산으로 해결되게 된다.
  • 총 시간복잡도는 O(E*α(V) + QlogQ)이다

오프라인/병렬이분탐색

  • 특별한 아이디어가 필요하지는 않고, 그냥 병렬 이분 탐색 (Parallel Binary Search; PBS)의 프레임워크에 맞춰서 돌리면 된다.
  • 그냥 적용하면 시간복잡도는 O(logE*(E*α(V) + Q*α(V)) = O(logE*(E+Q)*α(V))가 된다
  • 시간 향상시킬수 있는 약간의 팁은, E개의 엣지들에 대해서 연결 안됐으면 추가, 연결되어있으면 패스하는 작업을 logE번 하는 대신에, 처음에 한번 시뮬레이션을 돌려서 실제로 추가가 될 V개의 엣지들을 미리 골라놓는 것이다. 그러면 V개의 엣지를 추가하는 것을 logV번 하는 것으로 처리할수 있다
  • 시간 복잡도는 O(E*α(V) + logV*(V*α(V)+Q*α(V))) = O(E*α(V)+(Q+V)logV*α(V))가 된다

트리에서의 동적 연결성

엣지를 삭제하는 쿼리만 들어올 때

  • 오프라인 쿼리가 가능하다면, 그냥 모든 쿼리를 역순으로 처리하면 엣지를 추가하는 쿼리만 들어오는 경우를 처리하는 것과 동일하다. 똑같이 Disjoint Set을 이용해서, 연결성 확인과 엣지 추가(실제로는 삭제)를 O(α(n))에 처리할 수 있다.
  • 온라인으로만 처리해야 한다면 풀 수 있는 방법이 여러가지 존재한다.
    • 경로 쿼리로 처리하는 방법
      • 시간 복잡도: 연결성 확인 O(log^2(n)), 엣지 삭제 O(logn)
      • 필요한 것: Fenwick Tree, Heavy-light decomposition
    • 서브트리 쿼리로 처리하는 방법
      • 시간 복잡도: 연결성 확인 O(logn), 엣지 삭제 O(logn)
      • 필요한 것: Xor Fenwick Tree (or Segment Tree with Lazy propagation), Euler tour technique
    • 서브트리의 노드 값을 일일히 바꿔주는 방법
      • 시간 복잡도: 연결성 확인 O(1), 엣지 삭제 amortized O(logn)
      • 필요한 것: 없음
  • 트리와 트리 문제로 테스트해본 결과 실제 실행 시간은 시간복잡도 순서와 일치하지는 않았다.
    • [오프라인 쿼리] O(n+q*α(n)) < [서브트리쿼리 + 펜윅트리] (O(n+qlogn)) < [경로쿼리 + 펜윅트리] (O(n+qlog^2n)) < [서브트리쿼리 + 레이지 세그트리] (O(n+qlogn)) < [노드값 일일히 바꾸기] (O(n+q+nlogn)) 순서였다.
    • [노드값 일일히 바꾸기] 방법은 열심히 최적화를 시도했지만 TLE 벗어나지 못했다.

경로 쿼리로 처리하는 방법

  • 엣지를 삭제하는 쿼리는 엣지에 삭제 표시만 해주는 것으로 처리하고, u와 v의 연결성을 묻는 쿼리는 u에서 v까지의 경로상에 삭제표시된 엣지가 존재하는지를 찾는 것으로 처리할 수 있다.
  • 트리에서의 경로 쿼리이므로, 당연하게 Heavy light decomposition을 떠올릴 수 있다.
  • HLD로 경로를 구간으로 바꾸어, 구간 쿼리로 처리하면 된다. 엣지의 초기값을 0, 삭제되면 1로 바꿔준 다음, 경로안의 엣지의 합이 0인지 체크하는 구간합 쿼리를 사용하면 된다.

서브트리 쿼리로 처리하는 방법

  • 각 노드들에게 각각 어떤 그룹에 속하는지 그룹 ID를 할당해 준다. u와 v의 연결성을 묻는 쿼리는 u의 그룹ID와 v의 그룹ID가 동일한지 체크하는 것으로 처리된다.
  • parent[u]와 u 사이의 엣지를 삭제하는 것은 u를 루트로 하는 서브트리의 안의 노드들의 그룹ID를 parent[u]의 그룹 ID와 다른 값으로 할당해 주는 것으로 처리할 수 있다.
  • 서브트리에 대한 업데이트를 처리해야 하므로 Euler tour technique를 사용해서 서브트리를 구간으로 바꾸어서 구간 쿼리로 처리해야 한다.
  • 그러면, 처리해야 하는 것은 구간 업데이트와 포인트 쿼리가 되므로, 기본적으로는 Segment tree에 Lazy propagation을 적용해서 처리할 수 있다
    • 여기서 주의할 점은, assignment update를 써서 서브트리 전체를 동일한 값으로 할당해주면 안된다. 서브트리 안에서 이미 이전에 엣지 삭제 연산이 처리되어서 서브트리 안의 노드들이 여러가지 그룹ID를 갖고 있을 수 있다. parent[u]와 그룹ID가 같은 노드들에게만 새 그룹 ID를 할당해주어야만 한다. (안그러면 서브트리 안에서 이전에 쪼갠 그룹들이 다시 합쳐지게 된다.) 이것을 처리하는 방법은 새 그룹 ID를 u의 DFS ordering으로 만들어서 max update를 해주는 것이다. 그러면 서브트리 안에서 쪼개져있던 그룹들은 u의 DFS ordering보다 더 큰 그룹 ID를 갖고 있었을테니, max 연산으로는 바뀌지 않는다.
    • 이렇게 max 업데이트를 사용하면 lazy segment tree를 사용해서, 엣지 삭제와 연결성 체크를 각각 O(logn)에 할수 있다.
  • 그러나 쿼리 종류에 따라서는 구간 업데이트와 포인트 쿼리를 포인트 업데이트와 구간 쿼리로 변환할 수 있고, 이 경우에는 Lazy propagation이 필요 없으므로 더 빠르게 처리될 수 있다는 것을 알고 있다.
    • 구간 합으로 처리하는 방법은, 그냥 u이하의 노드들의 그룹ID에 전부 특정 값을 더해주는 것이다. 이러면 u이하의 노드들 중 그룹ID가 달랐던 노드들은 업데이트 이후에도 그룹 ID를 다르게 갖는다. 문제가 되는 것은 관계 없는 노드들이 우연히 같은 ID를 갖게 되는 것이다. 예를 들어 그냥 항상 1을 더해주기로 했다고 하자. 노드 s가 차일드 u, v를 갖고 있을때, (s,u)와 (s,v)를 모두 끊으면, s와 v, 또 s와 u는 다른 그룹ID를 갖지만, u와 v가 같은 ID를 갖게 되어서 연결된 것으로 처리된다. 이것을 방지하기 위해, 새로 값을 더해 만들어진 그룹ID가 기존에 존재하지 않았던 ID가 되게 하려면 매번 업데이트 할때마다 더하는 값을 1,2,4,8,.. 이렇게 늘려갈 수도 있지만 이렇게 하면 업데이트 몇번만 하면 그룹 ID값이 너무 커진다.
    • 대신에 u와 v의 그룹 ID가 같더라도 실제로 연결된 것이 맞는지를 확인하기 위해 추가로 lca(u,v)의 그룹 ID를 같이 체크해주는 방법이 있다. 이 세 노드가 모두 같은 그룹 id를 가질때만 연결된 것으로 체크하면 된다.
    • 좀더 기발한? 방법은.. 그냥 업데이트하는 값을 랜덤으로 정하는 것이다. 이때는 group ID의 최댓값을 고정시키려면 덧셈보다 XOR을 쓰는 것이 낫다. 그냥 int 범위에서 랜덤값을 만들어서 업데이트한다고만 생각해보자. 보통 문제들에서는 트리의 크기가 몇십만 단위이고, 모든 엣지가 다 끊어져서 각각이 전부 다른 그룹ID를 가져야 하는 상황이라고 쳐도, 몇십만개의 랜덤값중 같은 값이 확률은 가능성은 매우 낮다. 우연히 같은 값을 갖는 노드들이 있더라도 그 노드들에 대한 연결성 쿼리가 들어올 확률은 또 낮다. 이 방법을 쓰면 Lazy propagation을 처리할 필요도 없고 LCA를 계산할 필요도 없고 그냥 XOR펜윅트리 하나만으로 풀 수 있다.

서브트리의 노드 값을 일일히 바꿔주는 방법 - O(logn)

  • 노드마다 그룹ID를 부여한다는 기본 아이디어는 윗 방법과 동일하다.
  • 그러나 노드값 업데이트를 구간 쿼리로 처리하는 대신 그냥 하나하나 일일히 바꿔주는 것으로 처리하는 방법이다. 무식해보이고, 시간복잡도가 엄엄청 증가할것 같지만, small to large와 비슷한 메커니즘으로 amortized 로그 시간에 처리된다.
  • parent[u]와 u사이의 엣지를 끊으면 두 개의 그룹으로 나눠지게 되고, 이중에 한 그룹의 노드들에게는 새로운 그룹ID를 할당해줘야 한다. 이 때, 크기가 더 작은 그룹의 노드들을 업데이트 하는 것으로 결정하면, 업데이트 해야 하는 노드의 갯수는 {가장 큰 그룹의 크기}/2 이하이다.
  • k번의 엣지 삭제 연산을 처리한다고 했을때, 업데이트 해야 하는 노드의 갯수는 최악의 경우에도 n/2 + n/4 + n/4 + n/8 + n/8 + n/8 + n/8 + n/16 + … 이런식이 된다. k번의 삭제의 시간복잡도는 O(n/2 * logk) = O(nlogk). 엣지의 갯수는 전부 (n-1)이므로, 이 엣지들을 모두 삭제한다면 O(nlogn)이고, 삭제 한번의 연산은 amortized O(logn)으로 계산할 수 있다.

관련 문제

  • 트리 : 오프라인 쿼리 사용 가능
  • 트리 : 오프라인 쿼리 사용 불가.

오프라인 동적 연결성

  • TBD..

토론

댓글을 입력하세요:
C R D M D
 
ps/동적_연결성.txt · 마지막으로 수정됨: 2023/08/09 05:31 저자 teferi