关于树形结构:并查集

奢侈并查集

// 每个点的父亲节点
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];
}