andyli

题解 UVA11987 【Almost Union-Find】
本题三种操作第一种操作和第三种操作都可以使用加权并查集实现,使用指针存储并查集便可以实现第二种操作。 使用指针存...
扫描右侧二维码阅读全文
22
2019/07

题解 UVA11987 【Almost Union-Find】

本题三种操作第一种操作和第三种操作都可以使用加权并查集实现,使用指针存储并查集便可以实现第二种操作。
使用指针存储并查集时不建议使用$new$运算符,容易出错,比较常见的办法是初始一个内存池(比如代码中的$nodes$),初始化时便可直接使用。
代码如下:

#include <cstdio>
const int maxn = 100000;

struct Node {
    int num;
    Node *nxt, *prev, *parent, *tail;
} nodes[maxn];

void insert(Node* p, Node* root)
{
    p->parent = root;
    p->prev = root->tail;
    root->tail->nxt = p;
    p->nxt = nullptr;
    root->tail = p;
}

Node* find(int x)
{
    Node *px = nodes + x, *root = px->parent;
    while (root != root->parent)
        px->parent = (root = root->parent);
    return root;
}

void uni_set(int a, int b)
{
    Node *p = find(a), *q = find(b);
    if (p != q) {
        q->tail->nxt = p;
        p->prev = q->tail;
        q->tail = p->tail;
        for (Node* cur = p; cur; cur = cur->nxt)
            cur->parent = q;
    }
}

void move_set(int a, int b)
{
    Node *u = nodes + a, *p = find(a), *q = find(b);
    if (p == q)
        return;
    if (u == p) {
        Node *cur = u->nxt, *first = cur;
        if (cur) {
            cur->prev = nullptr;
            cur->tail = p->tail;
        }
        while (cur) {
            cur->parent = first;
            cur = cur->nxt;
        }
    } else {
        if (u == p->tail)
            p->tail = u->prev;
        u->prev->nxt = u->nxt;
        if (u->nxt)
            u->nxt->prev = u->prev;
    }
    insert(u, q);
}

void query_set(int p)
{
    long long num = 0, sum = 0;
    for (Node* cur = find(p); cur; cur = cur->nxt, num++)
        sum += cur->num;
    printf("%lld %lld\n", num, sum);
}

int main()
{
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        Node* cur = nodes + 1;
        for (int i = 1; i <= n; i++, cur++) {
            cur->num = i;
            cur->nxt = nullptr;
            cur->parent = cur;
            cur->tail = cur;
        }
        for (int i = 0; i < m; i++) {
            int opt, p, q;
            scanf("%d%d", &opt, &p);
            if (opt != 3)
                scanf("%d", &q);
            if (opt == 1)
                uni_set(p, q);
            else if (opt == 2)
                move_set(p, q);
            else
                query_set(p);
        }
    }
}
Last modification:November 6th, 2019 at 05:09 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment