Re: [闲聊] 高中入学的时候

楼主: Apache (阿帕契)   2018-04-09 23:27:11
※ 引述《Apache (阿帕契)》之铭言:
: 我入学前几天
: 为了救狗被车撞到
: 住院好几天
: 回去上课的时候同学都蛮熟了
: 打不进去小圈圈
: 成为边缘人

班上同学为了不让我发现这件事
决定不超过两个人一起行动
但是同一个圈圈的人还是会互相来往
像1号会跟2号讲话 2号会跟3号一起吃饭
代表同学1 2 3属于同一个圈圈
输入说明
每份资料第一行有两个数字N,Q,班上有N个同学,编后依序由1到N,而我依序做了Q次的
纪录,每一个纪录有下三种型式:
M a b 表示a和b被我观察到一起行动,也有可能a和b数字一样,代表单独行动
C x 表示我想知道编号x同学处在的圈圈大小为何。
Q a b 表示我想知道编号a与编号b是否处在同一个圈圈里,是就回答YES,否则回答NO。
保证:N<=10^5,Q<=4*10^5,由于记录档十分的巨大,你需要小心读取资料的时间。
输出说明
对于每个我想知道的询问输出一行,为我计算的正确答案会是多少。
范例输入1
3 4
C 1
M 1 2
C 1
Q 2 3
范例输出1
1
2
NO
范例输入2
4 7
M 1 2
M 2 3
M 3 1
C 2
Q 4 3
M 1 4
Q 2 4
范例输出2
3
NO
YES
作者: BoXeX (心爱骑士团异端审判骑士)   2018-04-09 23:29:00
作者: ken890126 (靈魂奸商 路西法)   2018-04-09 23:30:00
Code厨
作者: Ardt4113C (恋恋可爱)   2018-04-09 23:34:00
disjoint set?
作者: SecondRun (雨夜琴声)   2018-04-09 23:36:00
你在哪个班级有一万人的
楼主: Apache (阿帕契)   2018-04-09 23:37:00
那笔是观察全校用的==
作者: eatmycock (鸡鸡歪歪)   2018-04-09 23:39:00
哪一间学校有1万人的
楼主: Apache (阿帕契)   2018-04-09 23:41:00
114不过高中应该4不会那么大
作者: SecondRun (雨夜琴声)   2018-04-09 23:42:00
大学部+研究所应该很多有

Links booklink

Contact Us: admin [ a t ] ucptt.com