并查集

一个刷题的时候新学的数据结构。

题：2316. 统计无向图中无法互相到达点对数

对于并查集的解释可以看这篇：算法学习笔记(1) : 并查集

很适合处理分类问题，对于这道题也可以把所有连通的分到同一类，然后当前类的点数只记录在根节点即可。

同时可以使用路径压缩，也就是find的时候把父节点设置为根节点。

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
#include <iostream>
#include <cstdlib>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <stack>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <queue>
#include <numeric>
using namespace std;
// byd的头文件


class Union {
public:
    vector<int> fa;
    vector<int> sizes;

    Union(int n) : fa(n), sizes(n, 1) {  
        iota(fa.begin(), fa.end(), 0); // 每个节点的初始fa是其本身
    }

    int findFa(int x) {
        if (fa[x] == x) return x;
        else {
            return fa[x] = findFa(fa[x]); // 路径压缩
        }
    }

    void UnionCa(int x, int y) {
        int fx = findFa(x), fy = findFa(y);
        if (fx != fy) {
            if (sizes[fx] > sizes[fy]) {
                fa[fy] = fx;
                sizes[fx] += sizes[fy];
            } else {
                fa[fx] = fy;
                sizes[fy] += sizes[fx];
            }
        }
    }
};


class Solution {
public:
    long long countPairs(int n, vector<vector<int>>& edges) {
        Union myu(n);
        for (auto &edge : edges) {
            myu.UnionCa(edge[0], edge[1]);
        }
        long long res = 0;
        for (int i = 0; i < n; i++) {
            res += n - myu.sizes[myu.findFa(i)];
        }
        return res / 2; // 每个点对会被算两次，所以/2
    }
};