g727 - 蝸牛老師的冰棒

🔗 前往 ZeroJudge 原題

題目描述

題目描述了蝸牛老師懲罰臨末之頌的情境。蝸牛老師請 k 個學生吃冰棒，每個學生喜歡兩種口味的冰棒。臨末之頌需要找到一個學生排列方式，使得吃不到冰棒的學生數量最小。

解題思路

這道題可以建模為一個圖論問題。將每種冰棒口味視為一個節點，每個學生喜歡的兩種口味視為一條邊。題目要求找到一個學生排列方式，使得吃不到冰棒的學生數量最小，等價於找到圖中連通分量的數量。如果一個學生喜歡的兩種冰棒在同一個連通分量中，那麼他就能吃到冰棒。否則，他將無法吃到冰棒。

使用 Disjoint Set Union (DSU) 資料結構來追蹤連通分量。對於每個學生，如果他喜歡的兩種冰棒屬於不同的連通分量，則將這兩個連通分量合併。合併後，連通分量數量減少，意味著有更多的學生可以吃到冰棒。最終，吃不到冰棒的學生數量等於連通分量的數量。

程式碼中，ff 函數用於查找節點的根節點，merge 函數用於合併兩個連通分量。ans 變數用於記錄吃不到冰棒的學生數量。

複雜度分析

• 時間複雜度: O(k * α(n))，其中 k 是學生數量，n 是冰棒口味數量，α(n) 是反阿克曼函數，在實際應用中可以視為常數。
• 空間複雜度: O(n)，用於儲存 fa 陣列。

程式碼

#include <iostream>
using namespace std;
int n,ans,k,x,y,fa[100005];
int ff(int v){
	return fa[v]==v ? v:fa[v]=ff(fa[v]);
}
void merge(int x,int y){
	x=ff(x);
	y=ff(y);
	if(x==y){
		++ans;
		return;
	}
	fa[x]=y;
	return;
}
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> k;
	for(int i=0;i<n;++i){
		fa[i]=i;
	}
	for(int i=0;i<k;++i){
		cin >> x >> y;
		merge(x,y);
	}
	cout << ans;
}