poj1988;

Problem:

Cube Stacking
 Time Limit: 2000MS Memory Limit: 30000K Total Submissions: 11047 Accepted: 3697 Case Time Limit: 1000MS
Description
Farmer John and Betsy are playing a game with N (1 <= N <= 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1<= P <= 100,000) operation. There are two types of operations:
moves and counts.
* In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.
* In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value.
Write a program that can verify the results of the game.
Input
* Line 1: A single integer, P
* Lines 2..P+1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a 'M' for a move operation or a 'C' for a count operation. For move operations, the line also contains two integers: X and Y.For count operations, the line also contains a single integer: X.

Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself.
Output
Print the output from each of the count operations in the same order as the input file.
Sample Input
```6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4```
Sample Output
```1
0
2```
Source
USACO 2004 U S Open

Solution:

Disjoint set structure, find-union algorithms.
The solution is in the book of problem Galaxy.

SourceCode

:
//Mon Jun  7 15:51:10 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define MMAX 30001
using namespace std;

class Cube
{
public:
int parent; //The cube at the top of the stack;
int before; //The number of cubes above this cube.
int after; //The number of cubes under this cube, self inclusive;
};

vector<Cube> v(MMAX);

void Makeset(int N)
{
for (int i = 1; i <= N; i++)
{
v[i].parent = i;
v[i].before = 0;
v[i].after = 1;
}
}

int Find(int x)
{
//  int depth = 0;
//  int p = x;
//  while (p != v[p].parent)
//  {
//      p = v[p].parent;
//      depth++;
//  }
//
//  v[p].after = depth + v[x].after;
//  while (x != p)
//  {
//      int temp = v[x].parent;
//      v[x].parent = p;
//      v[x].before = depth--;
//      v[temp].after = v[x].after + 1;
//      x = temp;
//  }
//  return p;
int p = x;
if (p != v[p].parent)
{
int temp = v[p].parent;
v[p].parent = Find(temp);
v[p].before += v[temp].before;
}
return v[p].parent;
}

void Union(int x, int y)
{
int t1 = Find(x);
int t2 = Find(y);
if (t1 == t2)
return;
v[t2].parent = t1;
//  v[y].parent = t1;
//  v[x].after += v[t2].after;
//  if (x != t1)
//      v[t1].after += v[t2].after;
//  v[t2].before = v[t1].after;
//  if (y != t2)
//      v[y].before += v[t1].after;
v[t2].before += v[t1].after;
v[t1].after += v[t2].after;
}

int main(int argc, const char* argv[])
{
//  freopen("input.in", "r", stdin);
//  freopen("output.out", "w", stdout);
int N, P;
N = MMAX;
Makeset(N);
cin >> P;
for (int i = 0; i < P; i++)
{
char c;
int x, y;
cin >> c;
if (c == 'M')
{
cin >> x >> y;
Union(x, y);
//          cout << v[x].parent << ", " << v[x].before << ", " << v[x].after
//                  << endl;
//          cout << v[y].parent << ", " << v[y].before << ", " << v[y].after
//                  << endl;
}
else
{
cin >> x;
int t1 = Find(x);
cout << v[t1].after - v[x].before - 1 << endl;
}
}
//  fclose(stdin);
//  fclose(stdout);
return 0;
}