poj_1988_Cube_Stacking.cpp

Problem Links:

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;
}