# NOI China 2002: Legend of Galactic Heroes

## Original Problem Statement

4 M 2 3 C 1 2 M 2 4 C 4 2 Copy 样例输出1

-1 1 Copy 限制

2秒

## My translation (Redundant information removed)

There are 30K columns in a grid. There are also 30K numbered dots to be put and rearranged in the grid. Initially, only the nth dot is in the nth row. However, merge commands in the format "M i j" merges the contents of the column containing dot i and the column containing dot j together. After several merge commands, the grid is reformed. Another type of command, "C i j", queries whether or not dot i and dot j are in the same column. If so, then it returns the number of dots between i and j, if not, it returns -1. Write a program that parses and runs these commands.

## The Algorithm and Specifications

This problem uses an extended disjoint-set data structure. The normal DSDS is extended with two extra parameters, "before" and "count". These parameters store how many nodes are behind it in its tree (its height, or its location in a column) and how many nodes are in front of it. These parameters, being updated every find() and unify() call, accurately describe its location in its column. This is the core part of the problem apart for DSDS. My program describes the method in further depth through comments:

## The Code Itself

#include <cstdio>
#include <cstdlib>
using namespace std;

int father[30001],before[30001],count[30001]; // Define arrays: store ancestors, amount of nodes behind them or in front:
// <--before[node]------><{Node}------count[node]---->

void makeset()                                // Initialize set:
{
for (int i=1; i<=30000; i++)              // for each index initialize it for:
{
father[i]=i;                           // everyone is their own ancestor,
before[i]=0;                           // they are not connected,
count[i]=1;                            // and they are by themselves.
}
}
int find(int v)                               // Locate furthest ancestor process:
{
if(father[v]==v) return v;                // If it is the top of the tree (aka it is its own ancestor), then stop.
int b = father[v];                        // Else, record v's current ancestor,
father[v]=find(father[v]);                // update v's ancestor by going further up the tree,
before[v]=before[v]+before[b];            // and update the amount of nodes behind them.
return father[v];                         // The answer is the updated ancestor variable
}
void unify(int x, int y)                      // Merge x and y tree process:
{
int fx,fy; fx=find(x); fy=find(y);        // Locate the tree roots.
if (fx==fy) return;                       // Who merges the same trees?
father[fx]=fy;                            // Connect them,
before[fx]+=count[fy];                    // and update their location in the tree,
count[fy]+=count[fx];                     // and their depth in the tree.
}
int main()                                    // The main process:
{
int n; scanf("%d\n",&n);                  // Read the command amount,
makeset();                                // plant the forest,
for(int i=0;i<n;i++)                      // and read the commands:
{
char c; int p1, p2;                   // The character c is the command type and p1 and p2 are parameters
scanf("%c %d %d\n",&c,&p1,&p2);       // We read them, noting the newline,
if(c=='M') unify(p1,p2);              // and parse command types: c="M" means unify p1 and p2
else if(c=='C')                       // while c="C" requests the fruit distance between p1 and p2.
{
if(find(p1)==find(p2)) printf("%d\n", abs(before[p1]-before[p2])-1);
else printf("-1\n");              // If undefined, the answer is -1
}
}

}