关于树形结构:并查集

奢侈并查集

// 每个点的父亲节点int p[N];// 每个汇合的大小int sz[N];void init(int n) {    for (int i = 1; i <= n; i ++ ) {        p[i] = i;        sz[i] = 1;    }}int find(int x) {    if (p[x] != x) p[x] = find(p[x]);    return p[x];}void merge(int x, int y) {    x = find(x), y = find(y);    p[x] = y;    sz[y] += sz[x];}

带门路压缩的并查集

// 每个点的父亲节点int p[N];// 每个点间隔根节点的间隔int dist[N];// 每个汇合的大小int sz[N];void init(int n) {    for (int i = 1; i <= n; i ++ ) {        p[i] = i;        dist[i] = 0;        sz[i] = 1;    }}int find(int x) {    if (p[x] == x) return x;    int root = find(p[x]);    d[x] += d[p[x]];    return p[x] = root;}void merge(int x, int y) {    x = find(x), y = find(y);    p[x] = y;    d[x] = sz[y];    sz[y] += sz[x];}