POJ 1988 -- Cube Stacking


http://poj.org/problem?id=1988
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

除了parent数组,还要开设 under数组,under[i]表示第i个方块下面有多少个方块。 under数组在堆合并和路径压缩的时候都要更新。

const int maxn = 30010;
int parent[maxn],under[maxn];
 
int find(int t)
{
    if(parent[t]<0)
        return t;
    int s=find(parent[t]);
    under[t]+=under[parent[t]];
    parent[t]=s;
    return s;
}
void merge(int l,int r)
{
    int u = find(l);
    int d = find(r);
    if(u==d)
        return;
    under[u]=-parent[d];
    parent[d]+=parent[u];//将子集成员个数加起来
    parent[u]=d;
}
int main()
{
    freopen("in.txt","r",stdin);
    int p,l,r,t;
    char c,str[10];
    memset(parent,-1,sizeof(parent));
    scanf("%d",&p);
    while(p--)
    {
        //getchar();
        scanf("%s",str);
        if(str[0]=='M')
        {
            scanf("%d%d",&l,&r);
            merge(l,r);
        }
        if(str[0]=='C')
        {
            scanf("%d",&t);
            find(t);//输出前必须更新一下under数组
            printf("%d\n", under[t]);
        }
    }
}
http://www.cnblogs.com/Rinyo/archive/2013/02/23/2923686.html
一开始若干个元素自己为一个栈,给出n个操作,有如下两种:
    1.M a b :表示把元素a所在的栈整个压在含有元素b的栈的顶端
    2.C x :查询元素x所在的栈,x下方有几个元素,输出
  题意简单明了:并查集
  除了数组f[i]用来记录i的祖先,也就是顶端元素
  另需要数组rank[i],记录i所在的栈一共有多少个元素(i为栈顶)
       数组up[i],记录i上面有多少个元素
  则答案为rank[find(x)]-up[x]-1
至于在find和union中如何维护rank和up:
    在find中只需维护up,即up[x]+=up[father[x]];
    在union中需要维护up和rank,这时候rank起作用了。
    例如将x所在的栈压在y所在栈顶端,则y所在栈的顶端father[y]上元素的个数即为x所在栈所有元素个数,即up[father[y]]=rank[father[x]]
    (看了好多题解 表示不明白他们为什么要写up[father[y]]+=rank[father[x]],个人觉得用不着+啊,而且+不+都能AC...躺倒)
    而将x所在的栈压在y所在栈顶端后,x所在栈的总元素个数将会加上y所在栈元素个数,即rank[father[x]]+=rank[father[y]
http://www.cnblogs.com/lvpengms/archive/2010/02/03/1662792.html
* 应用 并查集的思路,移动一个栈时,相当于union_set操作,只要另开一个
* 数组记录立方体的位置,当合并时,只要改变根节点的位置记录就可以了,
* 这个地方并查集用的比较巧妙。其余的就是基本的并查集操作了
int cube[30330],nr[30330];int n;void make_set()
{
    
for(int i=0;i<=30030;++i)
    {
        cube[i] 
= -1;
        nr[i] 
= 0;
    }
}
int find_set(int x)
{
    
int tmp = cube[x];
    
if(cube[x]<0)
        
return x;
    cube[x] 
= find_set(cube[x]);
    nr[x] 
+= nr[tmp];
    
return cube[x];
}
void union_set(const int& root1,const int& root2)
{
    
int tmp = cube[root1];
    cube[root1] 
= root2;
    nr[root1] 
=nr[root1] - cube[root2];
    cube[root2] 
+= tmp;
}
int main()
{
    
int i,j,root1,root2,n1,n2;
    
char ch[1];
    cin
>>n;
    make_set();
    
while(n--)
    {
        scanf(
"%s ",ch);  
        
if(ch[0]=='M')
        {
            scanf(
"%d%d",&n1,&n2);
            
int root1 = find_set(n1);
            
int root2 = find_set(n2);
            
if(root1!=root2)
                union_set(root1,root2);
        }
else if(ch[0]=='C')
        {
            scanf(
"%d",&n1);
            
int tmp =find_set(n1);
            printf(
"%d\n",nr[n1]);
        }
    }
    
return 0;
}


Also check http://www.csdn123.com/html/blogs/20130522/15411.htm
Read full article from 1988 -- Cube Stacking

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts