UVALive 6910 Cutting Tree 并查集

Cutting Tree 并查集

Source

UESTC 2016 Summer Training #19

UVALive 6910

My Solution

简单并查集

给出一片森林， 然后执行

1）切断 x和x的父节点的边，    //  查询的时候不进行路径压缩， 然后直接 father[ x] = x

2）查询 x， y 是否是相连通的 //分别找x y的根， _find(x) == _find(y)

复杂度 O(n)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 2*1e5 + 8;


int father[maxn], _rank[maxn], sz[maxn], trees[maxn];
bool flag;
inline void DisjointSet(int n)
{
    for(int i = 0; i <= n; i++){
        father[i] = i;
        trees[i] = 1;
    }
}

int x, y;

int _find(int v, int u)  //请忽略这个 _find()
{
    if(father[v] == u) return -1;
    return father[v] == v ? v : _find(father[v], u);
}

int _find(int v)
{
    //if(father[v] == u) return -1;
    return father[v] == v ? v : _find(father[v]);
}


int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("b.txt", "w", stdout);

    #endif // LOCAL
    int T, n, k, val, u, kase = 0;
    char op;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i++){
            scanf("%d", &val);
            if(val != 0) father[i] = val;
            else father[i] = i;
        }

        printf("Case #%d:n", ++kase);
        while(k--){
            getchar(); //!!!!!!
            scanf("%c", &op);
            if(op == 'C'){
                scanf("%d", &u);
                father[u] = u;
            }
            else{
                scanf("%d%d", &x, &y);
                if(_find(x) == _find(y)) printf("YESn");
                else printf("NOn");
            }
        }
    }

    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx