b413: 虛擬女友:
內容：
曾經有一部採訪影片《BBC 紀錄片：別和日本人談性 No Sex. We're Japanese.》在網路上流傳，其中有一段談到虛擬遊戲中的生活，不少男性以遊戲中的女角發生關係，其中以一款遊戲「Love Plus」為大宗，即使是擁有現實和虛擬的生活，若要選擇其中一方站，不少男性仍然「我選擇死亡」回答。
現在先不解決男女雙方的問題、在彼此關係上要如何運作，如何回到早些年沒有遊戲機、沒有網路、更沒有虛擬女友的交際生活，只有同性朋友要怎麼交流呢？於是有一場專門為這些男性舉行的一場交友會，規則如下所述：
一開始全場男性都彼此不認識
每一個男性分別喜歡各自的虛擬女友 (可以是同一個)
每一個時刻，其中兩個男性會因談論遊戲而成為朋友
自己朋友的朋友也會成為朋友
如果朋友的虛擬女友的類型不同，他們有可能會因偏好女友類型不同而爭吵，稱為不穩定對。
請問每一個時刻下，有多少穩定對朋友。
輸入說明 ：
第一行會有一個 T，表示接下來會有幾組測資。
每一組測資第一行會有兩個整數 N,M，表示會場有 N 名男性以及會場會有 M 個時刻。接下來會有一行 N 個整數 Ai，表示第 i 名男性的偏好虛擬女友類型。
接下來會有 M 行，每一行上會有兩個整數 x,y，第 i 行表示時刻 i 男性 x,y 成為朋友關係。
- 1≤x,y,Ai≤N
- 1≤N,M≤50000
輸出說明：
對於每一個時刻，輸出穩定朋友對。
範例輸入：
3 2 1 2 1 1 2 2 3 4 4 1 2 2 1 1 2 2 3 1 3 2 4
範例輸出：
0 1 0 1 1 2
提示：
第一組測資
時刻 1，沒有任何一組。
時刻 2，(1, 3) 是一組穩定對，因為他們都喜歡類型 1 的。
第二組測資
時刻 1，沒有任何一組。
時刻 2，(2, 3) 是一組穩定對。
時刻 3，(2, 3) 是一組穩定對。
時刻 4，(2, 3) 和 (1, 4) 是一組穩定對。
標籤:
并查集
#include <stdio.h>
#include <algorithm>
#define MAXN 1000005
int parent[MAXN];
int size[MAXN];
int girlfriend[MAXN];
int t,n,m;
int tmp;
int tmp_a,tmp_b;
int stable = 0;
void MAKE_SET(int x){
parent[x] = x;
size[x] = 1;
}
void init(int n){
for(int i=0;i<n;i++){
MAKE_SET(i);
}
}
int FIND_SET(int x){
if (parent[x]==x)return x;
parent[x]=FIND_SET(parent[x]);
return parent[x];
}
bool UNION(int x,int y){
x = FIND_SET(x);
y = FIND_SET(y);
if (x==y)return false;
if (size[x]<size[y]){
std::swap(x,y);
}
parent[y] = x;
size[x]+=size[y];
return true;
}
int stablecount(){
stable = 0;
for(int i=1;i<=n-1;i++){
for(int j=i+1;j<=n;j++){
if ( girlfriend[i]==girlfriend[j] && FIND_SET(i)==FIND_SET(j))stable++;
}
}
return stable;
}
int main(){
scanf("%d",&t);
for (int i=0;i<t;i++){//t 測資
scanf("%d%d",&n,&m);
init(n);
for(int i=1;i<=n;i++){//女友類型 girlfriend[x] 是喜歡的類型
scanf("%d",&tmp);
girlfriend[i] = tmp;
}
for (int i=0;i<m;i++){ //時刻 m 個
scanf("%d%d",&tmp_a,&tmp_b);
UNION(tmp_a,tmp_b);
tmp = stablecount(tmp_a,tmp_b);
printf("%d\n",tmp);
}
}
}