一路数据结构题 想了很久 并查集
一道数据结构题 想了很久 并查集？
有n个独立的磁铁(1,2,⋯n标号)放在桌上，一个人对这n堆进行移动操作，然后另一个人询问。
有以下规则：
M X Y : 将含有编号X的磁铁块放在包含Y的磁铁块的顶端。（磁铁块指很多磁铁吸在了一起）
C X : 询问在编号X磁铁下的磁铁的数目。
Input Format
第1行一个整数，操作数p。
第2行到第p+1行：每一行是个合法操作，形如M X Y或C X。
Output Format
对于每个C操作输出一行，即对应的磁铁数。
Sample Input
Sample Output
About Test Data
就是这样一道题目，请问该怎么做呢？并查集？
十分感谢大家！
------解决方案--------------------
方法一：数据分为两部分，磁铁数组和磁铁组表。
磁铁数组包含所有磁铁信息，磁铁信息中有磁铁组号（或指针）、该铁在组中的位置（就是其下有多少磁铁。
磁铁组是个线性表，元素是磁铁号，只要求遍历、添加、合并功能，用链表实现。
初始化：所有磁铁，位置为0；为所有磁铁创建单元磁铁组表。
M命令：找到X所在磁铁组GX、,O(1)操作；
找到Y所在磁铁组GY，O(1)操作；
遍历GX中的元素，将对应磁铁信息中的磁铁组号（或指针）改为GY，位置加上Length(GY)，O（N）操作
GY合并到GX中，O(1)操作。
C命令：输出X中的位置信息
初始化时可以不创建磁铁组表，这样就要在M命令中进行判断，分别对GX和GY为空时进行处理
------解决方案--------------------
方法二：
磁铁信息使用链接信息，同组磁铁组成链表，需要能够通过任一元素找到链表首尾，可以使用双向链，或者使用带头标志的循环链。下面用双向链为例：
初始化：所有磁铁prev=null,next=null
M命令：
找到Y所在链表首HY,O(N)
找到X所在链表尾TX,O(N)
连接两个链表,O(N)
C命令：
找到从X遍历到链表尾并计数，O(N)
可以在磁铁信息中保存“其下磁铁数”的信息以加快C命令：
在M命令的第一步时，可以计算出Y链表的长度（Y中的位置信息+遍历过的节点数）
在M命令的第二步时，先找到X所在链表首，再遍历到链表尾，所有节点的位置信息+Y链表长度
------解决方案--------------------
并查集无误。合并的时候多做几步操作就是。
1L 2L的办法总复杂度都会退化到平方的。数据很好构造。
本帖最后由 u010971328 于 2013-07-03 09:14:27 编辑
Description有n个独立的磁铁(1,2,⋯n标号)放在桌上，一个人对这n堆进行移动操作，然后另一个人询问。
有以下规则：
M X Y : 将含有编号X的磁铁块放在包含Y的磁铁块的顶端。（磁铁块指很多磁铁吸在了一起）
C X : 询问在编号X磁铁下的磁铁的数目。
Input Format
第1行一个整数，操作数p。
第2行到第p+1行：每一行是个合法操作，形如M X Y或C X。
Output Format
对于每个C操作输出一行，即对应的磁铁数。
Sample Input
6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
Sample Output
1
0
2
About Test Data
对于全部数据：1≤n≤30000;1≤p≤100000
对于50%的数据: 1≤n≤1000;1≤p≤10000
就是这样一道题目，请问该怎么做呢？并查集？
十分感谢大家！
数据结构
------解决方案--------------------
方法一：数据分为两部分，磁铁数组和磁铁组表。
磁铁数组包含所有磁铁信息，磁铁信息中有磁铁组号（或指针）、该铁在组中的位置（就是其下有多少磁铁。
磁铁组是个线性表，元素是磁铁号，只要求遍历、添加、合并功能，用链表实现。
初始化：所有磁铁，位置为0；为所有磁铁创建单元磁铁组表。
M命令：找到X所在磁铁组GX、,O(1)操作；
找到Y所在磁铁组GY，O(1)操作；
遍历GX中的元素，将对应磁铁信息中的磁铁组号（或指针）改为GY，位置加上Length(GY)，O（N）操作
GY合并到GX中，O(1)操作。
C命令：输出X中的位置信息
初始化时可以不创建磁铁组表，这样就要在M命令中进行判断，分别对GX和GY为空时进行处理
------解决方案--------------------
方法二：
磁铁信息使用链接信息，同组磁铁组成链表，需要能够通过任一元素找到链表首尾，可以使用双向链，或者使用带头标志的循环链。下面用双向链为例：
初始化：所有磁铁prev=null,next=null
M命令：
找到Y所在链表首HY,O(N)
找到X所在链表尾TX,O(N)
连接两个链表,O(N)
C命令：
找到从X遍历到链表尾并计数，O(N)
可以在磁铁信息中保存“其下磁铁数”的信息以加快C命令：
在M命令的第一步时，可以计算出Y链表的长度（Y中的位置信息+遍历过的节点数）
在M命令的第二步时，先找到X所在链表首，再遍历到链表尾，所有节点的位置信息+Y链表长度
------解决方案--------------------
并查集无误。合并的时候多做几步操作就是。
1L 2L的办法总复杂度都会退化到平方的。数据很好构造。