a531. [模板] 並查集 DSU - 彰化精誠中學

內容

給定$N$個元素，初始時每個元素都在獨立的集合(1號元素在集合1,2號元素在集合2,...)。
之後會有$M$次操作，操作分以下兩種:

1 $x$ $y$ 合併$x$和$y$所在的集合，若$x$和$y$已在同一集合則略過

2 $x$ $y$ 若$x$和$y$在同一集合，輸出該集合中有多少個元素，若$x$和$y$不在同一集合則輸出-1

輸入說明

第一行有兩個整數$N$和$M$($N\le 2\times 10^5$,$M\le 4\times 10^5$)，代表初始有$N$個元素和集合，之後會有$M$次操作。

接下來M行每行有三個整數$op_i$ $x_i$ $y_i$

($op$ $\epsilon \{1,2\}$, $1\le x,y \le N$)

若$op_i$為1則 : 合併$x$和$y$所在的集合，若$x$和$y$已在同一集合則略過

若$op_i$為2則 : 若$x$和$y$在同一集合，輸出該集合中有多少個元素，若$x$和$y$不在同一集合則輸出-1

輸出說明

對於每個2操作輸出題目要求的答案，輸出後換行。

範例輸入 #1

範例輸出 #1

-1
3

範例輸入 #2

範例輸出 #2

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (10%): 1.0s , <1M
公開測資點#1 (10%): 1.0s , <1M
公開測資點#2 (10%): 1.0s , <1M
公開測資點#3 (10%): 1.0s , <1M
公開測資點#4 (10%): 1.0s , <10M
公開測資點#5 (10%): 1.0s , <10M
公開測資點#6 (10%): 1.0s , <10M
公開測資點#7 (10%): 1.0s , <10M
公開測資點#8 (10%): 1.0s , <10M
公開測資點#9 (10%): 1.0s , <10M

提示：

標籤:

DSU

出處:

經典 [管理者：

211096@stu.c... (唐狗針)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」