사용자 도구

사이트 도구


ps:동적_연결성

동적 연결성

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

트리에서의 동적 연결성

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

  • 오프라인 쿼리가 가능하다면, 그냥 모든 쿼리를 역순으로 처리하면 엣지를 추가하는 쿼리만 들어오는 경우를 처리하는 것과 동일하다. 간단하게 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 + 4/n + 4/n + 8/n + 8/n + 8/n + 8/n + 16/n + … 이런식이 된다. k번의 삭제의 시간복잡도는 O(2/n * logk) = O(nlogk). 엣지의 갯수는 전부 (n-1)이므로, 이 엣지들을 모두 삭제한다면 O(nlogn)이고, 삭제 한번의 연산은 amortized O(logn)으로 계산할 수 있다.

관련 문제

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

오프라인 동적 연결성

  • TBD..

토론

댓글을 입력하세요:
A E​ S L Q
 
ps/동적_연결성.txt · 마지막으로 수정됨: 2021/05/24 14:49 저자 teferi