传送门
题意:
给你两个相同数量点的森林,问你最多能在两个森林中加多少相同的边。
思路:
两个循环即可搞定,用并查集判断加入边
<
i
,
j
>
<i,j>
<i,j>后是否存在环。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
#include<math.h>
using namespace std;
#define ll long long
#define mod 998244353ll
int f1[1010], f2[1010];
int find1(int x)
{
return f1[x]==x? x : f1[x]=find1(f1[x]);
}
int find2(int x)
{
return f2[x]==x? x : f2[x]=find2(f2[x]);
}
struct node{
int x,y;
};
queue<node>q;
int main()
{
int n,m1,m2;
cin>>n>>m1>>m2;
for(int i = 1; i <= n; i++)f1[i] = f2[i] = i;
while(m1--)
{
int u,v;
cin>>u>>v;
f1[find1(u)] = find1(v);
}
while(m2--)
{
int u,v;
cin>>u>>v;
f2[find2(u)] = find2(v);
}
for(int i = 1; i <= n; i++)
{
for(int j = i+1; j <= n; j++)
{
if(find1(i) != find1(j) && find2(i) != find2(j))
{
node now;
now.x = i,now.y = j;
q.push(now);
f1[find1(i)] = find1(j);
f2[find2(i)] = find2(j);
}
}
}
cout<<q.size()<<endl;
while(!q.empty())
{
node now = q.front();
q.pop();
cout<<now.x<<" "<<now.y<<endl;
}
}
|