C - Roads and Libraries HackerRank - torque-and-development 【 并查集 】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn =100005;
ll fa[maxn];
ll fin(ll x)
{
    return x == fa[x] ? x : fa[x] = fin(fa[x]);
}
void Un(ll x, ll y)
{
    ll a = fin(x);
    ll b = fin(y);
    if(a != b)
    {
        fa[a] = b;
    }
    return ;
}
int main()
{
    ll t,u,v;
    ll n,m,croad,clib;
    scanf("%lld", &t);
    while(t--)
    {
        scanf("%lld %lld %lld %lld", &n, &m, &clib, &croad);
        ll num = 0;
        num = n * clib;

        for(ll i = 1; i <= n; i ++) fa[i] = i;
        for(ll i = 0; i < m; i ++)
        {
            scanf("%lld %lld", &u, &v);
            Un(u,v);
        }
        if(clib <= croad)
        {
            printf("%lld\n",num);
        }
        else
        {
            ll sum = 0;
            for(ll i = 1; i <= n; i ++)
            {
                if(fa[i] == i) sum += clib;
                else sum += croad;
            }
            printf("%lld\n",sum);
        }
    }
    return 0;
}