数据结构#

1
struct DSU
2
{
3
    ve<int>fa,p,e,f;
4
    DSU(int n)
5
    {
6
        fa.resize(n + 1);
7
        iota(fa.begin(), fa.end(), 0);
8
        p.resize(n + 1, 1);
9
        e.resize(n + 1);
10
        f.resize(n + 1);
11
    }
12
    int find(int x)
13
    {
14
        if(f[x]!=x) f[x]=find(f[x]);
15
        return f[x];
16
    }
17
    bool merge(int x, int y)
18
    {//y-->x
19
        if (x == y) f[find(x)] = 1; //之前已经在一个地方了
20
        x=find(x);y=find(y);
21
        e[x]++;//y-->x  边
22
        if (x == y) return false;
23
        if (x < y) swap(x, y); // 将编号小的合并到大的上
24
        fa[y] = x;
25
        f[x] |= f[y];//判断自环
26
        p[x] += p[y];//点
27
        e[x] += e[y];//边
28
        return true;
29
    }
30

31

32
    bool same(int x, int y) //判断是否在一个联通中
33
    {
34
        return find(x)==find(y);
35
    }
36
    bool F(int x) //判断x所在联通是否存在自环
37
    {
38
        return f[find(x)];
39
    }
40
    int size(int x) //获取点x所在联通的大小
41
    {
42
        return p[find(x)];
43
    }
44
    int E(int x) //联通中边的数量
45
    {
46
        return e[find(x)];
47
    }
48
};