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