b413. 虛擬女友
標籤 : 并查集
通過比率 : 24人/34人 ( 71% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-06-23 16:03

內容

曾經有一部採訪影片《BBC 紀錄片:別和日本人談性 No Sex. We're Japanese.》在網路上流傳,其中有一段談到虛擬遊戲中的生活,不少男性以遊戲中的女角發生關係,其中以一款遊戲「Love Plus」為大宗,即使是擁有現實和虛擬的生活,若要選擇其中一方站,不少男性仍然「我選擇死亡」回答。

現在先不解決男女雙方的問題、在彼此關係上要如何運作,如何回到早些年沒有遊戲機、沒有網路、更沒有虛擬女友的交際生活,只有同性朋友要怎麼交流呢?於是有一場專門為這些男性舉行的一場交友會,規則如下所述:

  • 一開始全場男性都彼此不認識
  • 每一個男性分別喜歡各自的虛擬女友 (可以是同一個)
  • 每一個時刻,其中兩個男性會因談論遊戲而成為朋友
  • 自己朋友的朋友也會成為朋友
  • 如果朋友的虛擬女友的類型不同,他們有可能會因偏好女友類型不同而爭吵,稱為不穩定對。

請問每一個時刻下,有多少穩定對朋友。

輸入說明
第一行會有一個 $ T $,表示接下來會有幾組測資。

每一組測資第一行會有兩個整數 $N, M$,表示會場有 $N$ 名男性以及會場會有 $M$ 個時刻。接下來會有一行 $N$ 個整數 $A_i$,表示第 $i$ 名男性的偏好虛擬女友類型。

接下來會有 $M$ 行,每一行上會有兩個整數 $x, y$,第 $i$ 行表示時刻 $i$ 男性 $x, y$ 成為朋友關係。

* $1 \le x, y, A_i \le N$
* $1 \le N, M \le 50000 $
輸出說明
對於每一個時刻,輸出穩定朋友對。
範例輸入 #1
2

3 2
1 2 1
1 2
2 3

4 4
1 2 2 1
1 2
2 3
1 3
2 4
範例輸出 #1
0
1
0
1
1
2
測資資訊:
記憶體限制: 64 MB
提示 :

第一組測資

  • 時刻 1,沒有任何一組。
  • 時刻 2,(1, 3) 是一組穩定對,因為他們都喜歡類型 1 的。

第二組測資

  • 時刻 1,沒有任何一組。
  • 時刻 2,(2, 3) 是一組穩定對。
  • 時刻 3,(2, 3) 是一組穩定對。
  • 時刻 4,(2, 3) 和 (1, 4) 是一組穩定對。
標籤:
并查集
出處:
IPSC2015 [管理者: morris1028 (碼畜) ]

本題狀況 本題討論 排行

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