[AtCoder - ABC279 F] BOX

난이도: 1777

 

태그

• Disjoint-Set Union

 

풀이

1. 1번 쿼리를 생각해보자.

\( i \)번 상자에 들어있는 공들의 집합을 \( S_{i} \)라고 합시다.

 

한 쪽 상자의 공을 다른 쪽 상자로 넣는 건, \( S_{X} \)와 \( S_{Y} \)를 합치는 것으로 표현해볼 수 있습니다.

두 집합을 합친다... 뭔가 DSU의 느낌이 나죠?

 

하지만 DSU에서 상자와 공을 둘 다 들고 있는 건 아무래도 무리가 있어 보입니다.

대신에, 상자를 빼고 공에 대해서만 DSU를 돌려봅시다.

 

만약 \( X \)번 상자에 있는 공 \( x \)와 \( Y \)번 상자에 있는 공 \( y \)를 알고 있다면,

이를 토대로 \( S_{x} \)와 \( S_{y} \)의 합집합을 구할 수 있겠죠.

 

그럼 문제는 공 \( x \)가 주어질 때, 무슨 상자에 있는 지 알아내는 작업입니다. (3번 쿼리와 동일하죠.)

 

2. 3번 쿼리를 생각해보자.

사실 어렵게 생각해보지 않아도 됩니다.

DSU를 하면서, 각 집합의 대표 정점마다 "이 정점이 들어있는 상자의 번호"를 적어주면 됩니다.

 

3. 구현 디테일

실제로 구현할 때는, 상자의 번호 → 들어있는 공 의 처리도 필요합니다.

이는 \( P_{i} \) = \( i \)번 상자의 대표 정점 으로 나타내면 됩니다.

만약 상자가 비어있다면 \( P_{i} = 0 \)으로 표현하겠습니다.

 

들어있는 공 → 상자의 번호 의 처리는

\( S_{x} \) = \( x \)번 공이 들어있는 상자 로 하겠습니다.

 

각각의 쿼리는, 아래와 같이 처리해주면 됩니다.

• 1번 쿼리
  • \( P_{X} = x, P_{Y} = y \)라고 하겠습니다.
  • 두 상자의 내용물이 합쳐지므로, \( \text{union}(x, y) \)를 해주면 됩니다.
    저의 경우는 \( \text{parent}[x] = y \)를 넣어줬습니다.
  • \( X \)번 상자의 대표 정점은, 합쳐진 집합의 대표자인 \( y \)가 됩니다.
  • \( Y \)번 상자는 이제 비어있을테니, \( P_{Y} = 0 \)이 됩니다.
  • 예외 처리: \( Y \)번 상자가 비어있다면, 존재하지 않는 \( y \)를 가지고 처리를 시도하게 됩니다.
    잘 있던 공들이 갑자기 존재하지 않는 공에 연결되어버리는 건 아무래도 좋지 않은 상황이죠.
  • 그런데 \( Y \)번 상자가 비어있다면, 그냥 아무 일도 없는 것과 다름없습니다.
    그러니 \( Y \)번 상자가 비어있을 때는 쿼리를 건너뛰어주면 됩니다.
• 2번 쿼리
  • \( P_{X} = x \)라고 하고, 새로 들어오는 공의 번호를 \( m \)이라고 하겠습니다.
  • 구현의 편의성을 위해, 새로운 공을 대표자로 만들어주면 됩니다.
  • 이 때 바뀌는 건 \( \text{parent}(x), P_{X}, S_{m} \)이 있겠네요.
• 3번 쿼리
  • \( S_{\text{find}(a)} \)를 찾아주면 됩니다.

 

4. 코드

pi2 par[600020];
int ptr[300020];
 
int fnd(int a){ return par[a].fr = (par[a].fr==a ? a : fnd(par[a].fr)); }
 
void Main(){
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n+q; i++){ par[i] = {i, i}; }
    for (int i = 1; i <= n; i++){ ptr[i] = i; }
    int m = n;
    while (q--){
        int typ; cin >> typ;
        if (typ == 1){
            int a, b; cin >> a >> b;
            if (ptr[b] == 0){ continue; }
            par[ ptr[a] ].fr = ptr[b]; ptr[a] = ptr[b];
            par[ ptr[b] ].sc = a; ptr[b] = 0;
        }
        if (typ == 2){
            int a; cin >> a; m += 1;
            par[ ptr[a] ].fr = m; ptr[a] = m;
            par[m] = {m, a};
        }
        if (typ == 3){
            int a; cin >> a;
            cout << par[fnd(a)].sc << endl;
        }
        /*cout << "PAR "; for (int i = 1; i <= m; i++){ cout << par[i].fr << ' ' << par[i].sc << "   "; }
        cout << endl;
        cout << "PTR "; for (int i = 1; i <= n; i++){ cout << ptr[i] << ' '; }
        cout << endl << endl << flush;*/
    }
}