ABC295G并查集强连通分量缩点

并查集合并到深度小的点，每次都选编号小的点做祖先即可。

为什么？因为题目说了，v能到u，即v是深度小的，从u和v路径上的点可以互相到达，用并查集合并即可。

#include <stdio.h>
#define N 200050
int n, m, i, j, k, a, b, p[N], f[N];
struct AB{
    int a, b, n;
} d[N];
int find(int x){
    if(x == f[x]) return x;
    return f[x] = find(f[x]);
}
int main(){
    scanf("%d", &n);
    for(i=1; i<=n; i++) f[i] = i;//强连通分量
    for(i=2; i<=n; i++){
        scanf("%d", &p[i]);//父亲
    }
    scanf("%d", &m);
    while(m--){
        scanf("%d%d", &k, &a);
        if(k == 1){
            scanf("%d", &b);
            a = find(a), b = find(b);
            while(find(a) != b){
                a = f[a];
                f[a] = find(p[a]);//深度小做祖先
            }//a和b不在同一个强连通分量，合并即可
        }
        else printf("%d\n", find(a));
    }
    return 0;
}