TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2103
  • 题目
  • P2103【并查集】The cubes
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    lynn 和 banana 用 N块相同的小立方块玩游戏,小方块编号为 1..N。开始时,小方块都单独分开的,每个看成一个柱子,即有N 柱子。lynn 要 banana 做 P个操作,操作有两种类型:
    (1) lynn 要求banana 把X号方块所在的柱子放到Y号所在的柱子上面,成一个新柱子。
    (2) lynn 要求 banana 计算X号方块所在柱子,它下面有多少个小方块。

    输入格式

    *第一行:一个整数P 𝑃
    *第 2..P+1 行:第i+1 行表示第i 个 FJ 要求的合法操作。如果这行以'M'开头,后面有两个整数x,y表示要进入(1)操作。 如果这行以'C'开头,后面有一个整数X,表示要求计算X所在柱子下面的方块个数。
    注:所有操作都是合法的。N并没有出现在输入文件中。

    输出格式

    依次要求计算的值,每次一行。

    样例输入

    6
    M 1 6
    C 1
    M 2 4
    M 2 6
    C 3
    C 4

    样例输出

    1
    0
    2

    提示

    1≤N≤ 30000,1≤P≤ 100000


    来源  hzoi