백준 28092 - 우선순위와 쿼리 (C++)

문제

• 문제 링크

  
   BOJ 28092 - 우선순위와 쿼리 
  

• 문제 요약

$N$개의 정점에 대해, 두 유형으로 이루어진 $Q$개의 쿼리를 처리하자.


• 제한

TL : $2$ sec, ML : $1024$ MB




$1 ≤ N, Q ≤ 10^5$

알고리즘 분류

• 자료 구조(data structures)
• 트리를 사용한 집합과 맵(tree _ set / map)
• 분리 집합(disjoint_set)

풀이

그래프끼리의 $Merge$를 빠르게 수행해야 한다.
나아가 각 그래프의 컴포턴트 개수도 관리해 주어야 한다.
이는 분리 집합을 이용해 간단하고 효율적으로 관리할 수 있다.

여기에 추가로, $2$번 쿼리의 조건을 만족하는 트리를 빠르게 구할 수 있어야 한다.
이는 삽입, 탐색, 삭제를 $O(logN)$ 수준으로 지원하는 $std::set$ 자료 구조를 이용해 처리할 수 있다.
$2$번 쿼리의 요구조건 그대로 정렬 기준을 커스텀 해주자.

---

어떤 그래프가 손절되어 앞으로 모든 쿼리에 영향을 주지 않을 조건은 결국 둘 중 하나다.

$1$번 쿼리에서 $Merge(u, v)$를 수행할 때, 사이클이 발생하는 경우.(트리가 아니게 됨)

$2$번 쿼리의 대상이 되는 경우.

두 번째 경우야 항상 $set$의 처음 요소일테니 간단하지만 첫 번째 경우는 조금 생각해봐야 한다.

$u, v$가 이미 같은 그래프에 속한 상황인데, 또 간선을 추가하게 되면 사이클이 발생한다.

$u, v$가 서로 다른 그래프에 속하지만, 둘 중 한 그래프가 사이클을 내포한 경우 나머지 한 그래프역시 트리가 아니게 된다.

---

결국 두 그래프가 $Merge$되어 새로운 트리로 탄생하는 경우는, 두 그래프 모두 사이클을 내포하지 않았던 경우이다.

나는 이를 일반화하여 작성하기 위해 우선 $Merge$함수에 진입 시 두 그래프를 모두 $set$에서 제거하였다.
이후 위의 조건을 모두 거치고도 살아 남았다면, 새로운 트리로 거듭날 수 있다는 것.

분리 집합을 다뤄봤다면 알겠지만 일관된 방향으로의 $Merge$와 $Size$ 전이도 올바르게 수행해주자.
사이클 판단을 위한 추가 배열을 운용하는 것이 편하다.

자세한 건 코드를 참조하자.

전체 코드

#include<bits/stdc++.h>
#define N 100001
using namespace std;
 
struct T
{
    int r, s;
    bool operator<(const T& t) const { return s ^ t.s ? s > t.s : r < t.r; }
};
vector <int> Par(N), Cy(N), Size(N, 1);
set <T> S;
 
int Find(int x) { return Par[x] = x == Par[x] ? x : Find(Par[x]); }
void Merge(int x, int y)
{
    S.erase({ x, Size[x] });
    S.erase({ y, Size[y] });
    Cy[x] += x == y;
 
    if (x ^ y)
    {
        if (Cy[x] + Cy[y]) Cy[x] = Cy[y] = 1;
        else
        {
            if (x > y) S.insert({ Par[x] = y, Size[y] += Size[x] });
            else S.insert({ Par[y] = x, Size[x] += Size[y] });
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
    for (int i(1); i <= n; i++)
        S.insert({ Par[i] = i, 1 });
 
    for (int i, u, v; q--;)
    {
        cin >> i;
        if (i & 1) cin >> u >> v, Merge(Find(u), Find(v));
        else cout << (*S.begin()).r << '\n', S.erase(S.begin());
    }
}

comment

끝