problem-solving/marriage-problem.cpp at master · yachShekhar/problem-solving · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll sz[2000001];
ll arr[2000001];
ll m[2000001];
ll w[2000001];
ll n, q1, q2, q3, x, y;

void init(ll n) {
    for (ll i = 0; i <= n; i++) {
        arr[i] = i;
        sz[i] = 1;
        if (i <= x) {
            m[i] = 1;
            w[i] = 0;
        } else {
            m[i] = 0;
            w[i] = 1;
        }
    }
}

ll root(ll i) {
    while (arr[i] != i) {
        i = arr[i];
    }
    return i;
}

bool find(ll A, ll B) {
    return root(A) == root(B);
}

void un(ll A, ll B) {
    ll ra = root(A);
    ll rb = root(B);

    if (ra == rb) {
        return;
    }

    if (sz[ra] >= sz[rb]) {
        arr[rb] = ra;
        sz[ra] += sz[rb];
        m[ra] += m[rb];
        w[ra] += w[rb];
    } else {
        arr[ra] = rb;
        sz[rb] += sz[ra];
        m[rb] += m[ra];
        w[rb] += w[ra];
    }
}

int main() {
    cin >> x >> y;
    n = x + y;
    init(n);
    cin >> q1;
    while (q1--) {
        ll a, b;
        cin >> a >> b;
        un(a, b);
    }
    cin >> q2;
    while (q2--) {
        ll a, b;
        cin >> a >> b;
        un(a + x, b + x);
    }
    cin >> q3;
    while (q3--) {
        ll a, b;
        cin >> a >> b;
        un(a, b + x);
    }

    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        if (arr[i] == i) {
            ll curr_men = m[i];
            ll remaining_women = y - w[i];
            ans += curr_men * remaining_women;
        }
    }
    cout << ans << endl;
    return 0;
}