Problème : Cube Stacking

Lien : http://poj.org/problem?id=1988

Énoncé

Farmer John et Betsy jouent à un jeu avec N (1 ≤ N ≤ 30 000) cubes identiques numérotés de 1 à N. Ils commencent avec N piles, chacune contenant un seul cube. Farmer John demande à Betsy d'effectuer P (1 ≤ P ≤ 100 000) opérations. Il existe deux types d'opérations : les déplacements et les comptages.

• Opération de déplacement : Farmer John demande à Betsy de déplacer la pile contenant le cube X au-dessus de la pile contenant le cube Y.
• Opération de comptage : Farmer John demande à Betsy de compter le nombre de cubes dans la pile contenant le cube X qui se trouvent sous le cube X, et de siganler cette valeur.

Écrivez un programme capable de vérifier les résultats du jeu.

Entrée

• Ligne 1 : Un entier unique, P
• Lignes 2 à P+1 : Chacune de ces lignes décrit une opération valide. La ligne 2 décrit la première opération, etc. Chaque ligne commence par 'M' pour une opération de déplacement ou 'C' pour une opération de comptage. Pour les opérations de déplacement, la ligne contient également deux entiers : X et Y. Pour les opérations de comptage, la ligne contient un seul entier : X.

Notez que la valeur de N n'apparaît pas dans le ficheir d'entrée. Aucune opération de déplacement ne demandera de déplacer une pile sur elle-même.

Sortie

Imprimez le résultat de chacune des opérations de comptage dans le même ordre que le fichier d'entrée.

Exemple d'entrée

6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4

Exemple de sortie

1
0
2

Analyse

Le problème peut être抽象化为 la fusion d'ensembles de piles. Deux opérations sont définies :

• M : Déplacer la pile contenant X au-dessus de la pile contenant Y
• C : Compter le nombre d'éléments sous le cube X dans sa pile

Il s'agit d'un problème classique d'Union-Find avec compression de chemin. La solution utilise trois tableaux :

• parent[] : Stocke le nœud parent de chaque élément
• size[] : Stocke le nombre d'éléments dans l'ensemble dont l'élément est la racine
• dist[] : Stocke la distance entre l'élément et sa racine

Pour une requête de comptage sur le cube X, si root = find(X), alors le nombre d'éléments sous X est : size[root] - dist[X] - 1

Implémentation

#include "stdio.h"
#include "string.h"
#include "iostream"
#include "map"
#include "string"
#include "queue"
#include "stdlib.h"
#include "math.h"

#define MAX_N 30009
#define eps 1e-10
#define inf 1000000000
#define mod 2333333

using namespace std;

int parent[MAX_N];
int size[MAX_N];
int dist[MAX_N];

int find_root(int x)
{
    if (x != parent[x])
    {
        int t = parent[x];
        parent[x] = find_root(parent[x]);
        dist[x] += dist[t];
    }
    return parent[x];
}

void unite_stacks(int a, int b)
{
    int root_a = find_root(a);
    int root_b = find_root(b);
    
    if (root_a != root_b)
    {
        parent[root_b] = root_a;
        dist[root_b] += size[root_a];
        size[root_a] += size[root_b];
    }
}

int main()
{
    int operations, element_a, element_b;
    char operation_type[3];
    
    while (scanf("%d", &operations) != -1)
    {
        for (int i = 1; i <= MAX_N + 1; i++)
        {
            parent[i] = i;
            size[i] = 1;
            dist[i] = 0;
        }
        
        while (operations--)
        {
            scanf("%s", operation_type);
            
            if (operation_type[0] == 'M')
            {
                scanf("%d%d", &element_a, &element_b);
                unite_stacks(element_a, element_b);
            }
            else
            {
                scanf("%d", &element_a);
                int root = find_root(element_a);
                printf("%d\n", size[root] - dist[element_a] - 1);
            }
        }
    }
    
    return 0;
}

L'algorithme utilise la technique de compression de chemin lors de la recherche de la racine, ce qui permet d'optimiser les opérations successives. La fonction unite_stacks fusionne deux ensembles en mettant à jour les distances relatives et les tailles des composantes.