并查集+暴力
思路
并查集忘了o.o…
并查集分别维护两个森林,然后遍历每条边(i,j)并且判断在两个图中是否形成环(用并查集判断就行),如果没有形成环则说明可以添加该条边反之则不行.时间复杂度为O(n^2).
水题,复习一下并查集.
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
typedef pair<int,int> PII;
PII ans[N];
int fa1[N],fa2[N];
int n,m1,m2,cnt1,cnt2,res;
int get1(int x)
{
if(fa1[x]==x) return x;
return fa1[x]=get1(fa1[x]);
}
int get2(int x)
{
if(fa2[x]==x) return x;
return fa2[x]=get2(fa2[x]);
}
void merge1(int x,int y)
{
fa1[get1(x)]=get1(y);
cnt1++;
}
void merge2(int x,int y)
{
fa2[get2(x)]=get2(y);
cnt2++;
}
int main()
{
cin>>n>>m1>>m2;
for(int i=1;i<N;i++)
{
fa1[i]=i;
fa2[i]=i;
}
for(int i=1;i<=m1;i++)
{
int x,y;
cin>>x>>y;
merge1(x,y);
}
for(int i=1;i<=m2;i++)
{
int x,y;
cin>>x>>y;
merge2(x,y);
}
int counts=0;
for(int i=1;i<=n;i++)
{
if(cnt1==n-1||cnt2==n-1)
break;
for(int j=1;j<=n;j++)
{
int x1=get1(i),y1=get1(j);
int x2=get2(i),y2=get2(j);
if(x1!=y1&&x2!=y2)
{
merge1(x1,y1);
merge2(x2,y2);
ans[++counts]={i,j};
}
}
}
cout<<counts<<endl;
for(int i=1;i<=counts;i++)
cout<<ans[i].first<<" "<<ans[i].second<<endl;
return 0;
}