[数据结构与算法][luogu] P1682 过家家 并查集

前言

传送门 :

并查集过程不怎么难,难的是如果处理两个集合之间的关系

就是普通的并查集也没带权什么的

思路

题意大致看完之后,会发现其实我们需要维护的是所有集合之中含有最少男孩的数量+k

但是我们怎么样维护 一个集合中既有男孩又有女孩的数量呢 ,

我们不妨尝试使用$vis[x][y]$表示男孩$x$,女孩$y$,在合并的时候虽然男孩和女孩节点名字

相同但是我们任然可以直接合并,因为在我们计算的时候,我们只是使用女孩的而已

其实这题还是挺简单的(bushi
但是我选择的是维护男孩子的个数,女孩子的$sz$考虑为0,从而使得很多细节都难调最后爆炸了

Mycode

const int N  = 260;
int p[N];
bool vis[N][N];
int a[N];

int n,m,k,f;

int ans = 0x3f3f3f3f;

int find(int x){
	if(p[x] !=x) return p[x] = find(p[x]);
	return p[x];
}



void solve()
{
	cin>>n>>m>>k>>f;
	for(int i=1;i<=n;i++){
		p[i]= i;
	}
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
		vis[x][y] = 1;
	}
	
	for(int i=1;i<=f;i++){
		int x,y;cin>>x>>y;
		int fx = find(x);
		int fy = find(y);
		if(fx!=fy)
		p[fx] = fy;
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(vis[i][j]){
				vis[find(i)][j] = 1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(p[i] == i){
			int res = 0 ;
			for(int j=1;j<=n;j++)
				if(vis[i][j])
				++res;
			ans = min(ans,res);
		}
	}
	ans = min(ans+k,n);
	cout<<ans<<endl;
	
}