[数据结构与算法]CF1559D1 Mocha and Diana (Easy Version)（并查集

添加链接描述

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+9,M=2e3+9;
int n,m1,m2;
int h1[N],e1[M],ne1[M],idx1;
int h2[N],e2[M],ne2[M],idx2;
int fa1[N],fa2[N];
void add(int h[],int e[],int ne[],int idx,int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int find(int fa[],int x){
	if(fa[x]==x)return fa[x];
	return fa[x]=find(fa,fa[x]);
}
void merge(int fa[],int a,int b){
	fa[find(fa,a)]=find(fa,b);
}
typedef pair<int,int> pii;
vector<pii> ans;
int main(){
	scanf("%d%d%d",&n,&m1,&m2);
	memset(h1,-1,sizeof h1);
	memset(h2,-1,sizeof h2);
	for(int i=1;i<=n;i++){
		fa1[i]=i;
		fa2[i]=i;
	}
	for(int i=1;i<=m1;i++){
		int a,b;
		cin>>a>>b;
		add(h1,e1,ne1,idx1,a,b);
		add(h1,e1,ne1,idx1,b,a);
		merge(fa1,a,b);
	}
	for(int i=1;i<=m2;i++){
		int a,b;
		cin>>a>>b;
		add(h2,e2,ne2,idx2,a,b);
		add(h2,e2,ne2,idx2,b,a);
		merge(fa2,a,b);
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(find(fa1,i)!=find(fa1,j)&&find(fa2,i)!=find(fa2,j)){
				merge(fa1,i,j);
				merge(fa2,i,j);
				ans.push_back({i,j});
			}
		}
	}
	cout<<ans.size()<<endl;
	for(auto i:ans){
		cout<<i.first<<" "<<i.second<<endl;
	}
	return 0;
}