女友

b413: 虛擬女友:

內容:

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

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

一開始全場男性都彼此不認識
每一個男性分別喜歡各自的虛擬女友 (可以是同一個)
每一個時刻,其中兩個男性會因談論遊戲而成為朋友
自己朋友的朋友也會成為朋友
如果朋友的虛擬女友的類型不同,他們有可能會因偏好女友類型不同而爭吵,稱為不穩定對。
請問每一個時刻下,有多少穩定對朋友。
輸入說明 :
第一行會有一個 T,表示接下來會有幾組測資。

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

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

輸出說明:

對於每一個時刻,輸出穩定朋友對。

範例輸入:

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);
		}
	}
	
}

測資全對

卦長 Disjoint Sets 講義

IPSC 2015 F

演算法筆記 Disjoint Sets
pixiv