河南省第十六届icpc省赛

题目链接：https://ac.nowcoder.com/acm/contest/110308/C#:~:text=%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0,%E6%9D%A1%E4%BB%B6%EF%BC%9A%5B1%2C2%5D%2C%5B3%2C4%5D%E3%80%82

这是一道并查集+哈希表的题目

两个并查集分别构建小x和小y的联通；

由于：

for(int i = 1;i < n;i++){

for(int j = i;j <= n;j++){ 进行查找也行,但是是时间复杂度是O（n * n / 2）;

所以只能通过哈希表进行操作；

#include<vector>
#include<map>
using namespace std;
const int N = 2 * 1e6 + 10;
int fa1[N],fa2[N];
int find1(int x){
    if(fa1[x] != x){
        fa1[x] = find1(fa1[x]);
    }
    return fa1[x];
}
int find2(int x){
    if(fa2[x] != x){
        fa2[x] = find2(fa2[x]);
    }
    return fa2[x];
}
int main(){
    int n,m1,m2;
    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 aa,bb;
        cin >> aa >> bb;
        fa1[find1(aa)] = find1(bb);
    }
    for(int i = 1;i <= m2;i++){
        int aa,bb;
        cin >> aa >> bb;
      fa2[find2(aa)] = find2(bb);
    }
    map<pair<int,int>,int> count;
    for (int i = 1; i <= n; i++) {
        int root1 = find1(i);
        int root2 = find2(i);
        count[{root1, root2}]++;
    }
     long long ans = 0;
    for (auto &p : count) {
        int cnt = p.second;
        ans += 1LL * cnt * (cnt - 1) / 2; // C(cnt, 2)
    }
    
    cout << ans << endl;
    return 0;
}