[开发测试]D1. Mocha and Diana (Easy Version)

D1. Mocha and Diana (Easy Version)

题目链接🔗

题目大意
给你两个森林，让你对每个森林加相同的边，问你最多可以加多少条边

思路

怎么才能加边呢，这两个顶点没有连通才能加入，否则不能加入，那么根据树的定义可知连通意味着这两个点有相同的根且唯一，那么并查集再合适不过，然后暴力枚举$n?n$种结点组成情况，根据根或者说是否在同一个集合中判断能否加入

通过代码

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me(a) memset(a,0,sizeof(a)) 
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pi pair<ll,ll>
using namespace std;
const int N = 1e5+10;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
        
int tre[1010],tre1[1010];

int find1(int x){
    if(x!=tre[x])tre[x]=find1(tre[x]);
    return tre[x];
}

int find2(int x){
    if(x!=tre1[x])tre1[x]=find2(tre1[x]);
    return tre1[x];
}

int main(){

     int n,m1,m2;
     
     std::cin>>n>>m1>>m2;

        for(int i=1;i<=n;i++)tre[i]=i,tre1[i]=i;

        for(int i=1;i<=m1;i++){
             int u,v;
             std::cin>>u>>v;
             tre[find1(u)]=find1(v);
            }

        for(int i=1;i<=m2;i++){
            int u,v;
            std::cin>>u>>v;
            tre1[find2(u)]=find2(v);
        }
        std::vector<pi> t;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                int u1,v1,u2,v2;
                u1=find1(i),v1=find1(j);
                u2=find2(i),v2=find2(j);
                if(u1!=v1&&u2!=v2)
                    {
                        tre[u1]=v1;
                        tre1[u2]=v2;
                        t.pb({i,j});
                    }
            }
      }
        std::cout<<(int)t.size()<<'\n';
        for(auto x:t)std::cout<<x.fi<<' '<<x.se<<'\n';
           
     return 0;
}