14228: 【原4228】email

题目

题目描述

author: Shuhao Li 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4228

Description

同名区分问题在论文信息分析中是非常棘手的问题，同一个学者可能使用不同的名字形式发表论文，比如名字的缩写和全称，省略中间名。而不同学者可能又存在同名。在研究中经常会无法正确的识别出同名的不同人或是不同形式名字的同一个人。其中一个解决同名区分的方式就是使用邮箱。通常一个人的邮箱不太改变，而发论文一般都附带邮箱信息。

本题给出一些作者姓名和邮箱对应关系，你的任务是合并拥有相同邮箱的人。

Input Format

第一行包含一个正整数N，表示下面给出的姓名个数。

接下来N行每行给出一个名字（名字中没有空格且没有重名的人），然后接一个email地址。

Output Format

输出合并后的姓名组。一行一组，每组的姓名按照输入的先后顺序以空格隔开。

输出的组按照第一个姓名输入的顺序排序。

Sample Input

5
alice [email protected]
bob [email protected]
alicebest [email protected]
bob2 [email protected]
alice2016 [email protected]

Sample Output

alice alicebest alice2016
bob bob2

Limits

对于100%的数据，N<=100000。

不允许使用任何c++ stl容器库，例如map等。

BugenZhao's solution

//
// Created by BugenZhao on 2019/4/29.
//

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;
using ll = long long;


#ifndef SBL_BBINARYSEARCHTREE_H
#define SBL_BBINARYSEARCHTREE_H

template<typename Key, typename Val>
class BPair {
public:
    Key key;
    Val val;

    BPair(Key key, Val val) : key(key), val(val) {}

    BPair() = delete;
};

template<typename Key, typename Val>
class BBinarySearchTree {
    class Node {
    public:
        BPair<Key, Val> data;
        Node *left;
        Node *right;

        explicit Node(const BPair<Key, Val> &data, Node *left = nullptr, Node *right = nullptr) :
                data(data), left(left), right(right) {}
    };

    Node *root;
    int size;

private:
    BPair<Key, Val> *get(Node *node, const Key &key) {
        if (node == nullptr || node->data.key == key)
            return &node->data;
        if (key < node->data.key)
            return get(node->left, key);
        else
            return get(node->right, key);
    }

    void put(Node *&node, const Key &key, const Val &val) {
        if (node == nullptr)
            node = new Node({key, val});
        else if (key < node->data.key)
            put(node->left, key, val);
        else if (key > node->data.key)
            put(node->right, key, val);
        else
            node->data.val = val;
    }

    void remove(Node *&node, const Key &key) {
        if (node == nullptr)
            return;
        if (key < node->data.key)
            remove(node->left, key);
        else if (key > node->data.key)
            remove(node->right, key);
        else if (node->right == nullptr) {
            auto oldNode = node;
            node = node->left;
            delete oldNode;
        } else if (node->left == nullptr) {
            auto oldNode = node;
            node = node->right;
            delete oldNode;
        } else {
            auto p = node->right;
            while (p->left != nullptr) p = p->left;
            node->data = p->data;
            remove(node->right, node->data.key);
        }
    }

    void clear(Node *&node) {
        if (node == nullptr) return;
        clear(node->left);
        clear(node->right);
        delete node;
        --size;
    }

public:
    BBinarySearchTree() : root(nullptr), size(0) {}

    BPair<Key, Val> *get(const Key &key) {
        return get(root, key);
    }

    void put(const Key &key, const Val &val) {
        put(root, key, val);
    }

    void remove(const Key &key) {
        remove(root, key);
    }

    void clear() {
        clear(root);
    }

    virtual ~BBinarySearchTree() {
        clear();
    }
};


#endif //SBL_BBINARYSEARCHTREE_H

#ifndef SBL_BLINKEDLIST_H
#define SBL_BLINKEDLIST_H

#include <stdexcept>

template<typename Item>
class BLinkedList {
    class Node {
    public:
        Item item;
        Node *next;

        explicit Node(const Item &item, Node *next = nullptr) : item(item), next(next) {}

        explicit Node(Node *next = nullptr) : next(next) {}

        virtual ~Node() = default;
    };

    int N;
    Node *head;
    Node *tail;

    Node *getNode(int i) {
        Node *ret = head->next;
        while (i--) {
            ret = ret->next;
        }
        return ret;
    }

public:
    BLinkedList() {
        N = 0;
        head = new Node;
        tail = head;
    }

    BLinkedList(const BLinkedList &other) {
        N = 0;
        head = new Node;
        tail = head;
        auto p = other.head->next;
        while (head) {
            addLast(head->item);
        }
    }

    void clear() {
        if (tail == head) return;
        Node *p = head->next;
        Node *tmp;
        while (p) {
            tmp = p;
            p = p->next;
            delete tmp;
        }
        tail = head;
        N = 0;
    }

    virtual ~BLinkedList() {
        clear();
        delete head;
    }

    int size() const {
        return N;
    }

    void addLast(const Item &item) {
        auto node = new Node(item);
        tail->next = node;
        tail = node;
        ++N;
    }

    void addFirst(const Item &item) {
        auto tmp = head->next;
        auto node = new Node(item, tmp);
        head->next = node;
        ++N;
    }

    void insert(int i, const Item &item) {
        if (i == 0)
            addFirst(item);
        else if (i == N)
            addLast(item);
        else if (i >= N || i < 0)
            throw std::out_of_range("BLinkedList::insert out_of_range");
        else {
            auto p = getNode(i - 1);
            auto tmp = p->next;
            auto node = new Node(item, tmp);
            p->next = node;
            ++N;
        }
    }

    const Item &get(int i) {
        if (i >= N || i < 0)
            throw std::out_of_range("BLinkedList::get out_of_range");
        return getNode(i)->item;
    }

    void set(int i, const Item &item) {
        if (i >= N || i < 0)
            throw std::out_of_range("BLinkedList::set out_of_range");
        getNode(i)->item = item;
    }

private:
    class Iterator {
        Node *it;
        Node *head;
        Node *tail;
    public:

        Iterator(Node *head, Node *tail) :
                it(head), head(head), tail(tail) {}

        bool hasNext() const {
            return it != tail;
        }

        Item &next() {
            return (it = it->next)->item;
        }

        const Item &next() const {
            return (it = it->next)->item;
        }
    };

public:
    Iterator iterator() const {
        return Iterator(head, tail);
    }

    friend int main();
};

#endif //SBL_BLINKEDLIST_H

BLinkedList<string> *lists[100000] = {};
int count = 0;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;

    string name, email;
    BBinarySearchTree<string, BLinkedList<string> *> bst;
    BLinkedList<string> emails;

    while (N--) {
        cin >> name >> email;
        auto p = bst.get(email);
        if (p) p->val->addLast(name);
        else {
            emails.addLast(email);
            auto list = lists[count++];
            list = new BLinkedList<string>();
            list->addLast(name);
            bst.put(email, list);
        }
    }

    auto it = emails.iterator();
    while (it.hasNext()) {
        auto itt = bst.get(it.next())->val->iterator();
        while (itt.hasNext()) {
            cout << itt.next() << ' ';
        }
        cout << '\n';
    }

    auto p = lists;
    while (*p) {
        delete p;
        p += 1;
    }
    return 0;
}

skyzh's solution

#include <iostream>
#include <cstring>

using namespace std;

class NotFoundError {
};

class DuplicateKeyError {
};

struct String {
    const char *str;

    String(const char *str) : str(str) {}

    friend int cmp(const String &a, const String &b) {
        return strcmp(a.str, b.str);
    }
};

int cmp(int a, int b) {
    if (a < b) return -1;
    if (a == b) return 0;
    if (a > b) return 1;
}

template<typename T>
struct Vector {
    static const int VEC_DEF_SIZE = 16;
    int cap;
    int siz;
    T *data;

    Vector(T x) : cap(VEC_DEF_SIZE), siz(1), data(new T[cap]) { data[0] = x; }

    Vector() : cap(VEC_DEF_SIZE), siz(0), data(new T[cap]) {}

    void expand() {
        T *buffer = new T[cap * 2];
        memcpy(buffer, data, sizeof(T) * cap);
        cap *= 2;
        delete[] data;
        data = buffer;
    }

    void append(T x) {
        if (siz == cap) expand();
        data[siz++] = x;
    }
};

template<typename Key, typename T>
struct LLRB {
    struct Node {
        Key key;
        T x;
        Node *l, *r;
        bool is_red;

        Node(const Key &key, const T &x, Node *l = nullptr, Node *r = nullptr) : key(key), x(x), l(l), r(r),
                                                                                 is_red(true) {}

        friend bool is_red(const Node *ptr) {
            return ptr && ptr->is_red;
        }

        friend Node *rotate_left(Node *h) {
            Node *r = h->r;
            // assert(r->is_red);
            h->r = r->l;
            r->l = h;
            r->is_red = h->is_red;
            h->is_red = true;
            return r;
        }

        friend Node *rotate_right(Node *h) {
            Node *l = h->l;
            // assert(l->is_red);
            h->l = l->r;
            l->r = h;
            l->is_red = h->is_red;
            h->is_red = true;
            return l;
        }

        friend void flip_colors(Node *h) {
            // assert(!h->is_red);
            // assert(h->l->is_red);
            // assert(h->r->is_red);
            h->is_red = true;
            h->l->is_red = h->r->is_red = false;
        }
    } *root;

    LLRB() : root(nullptr) {}

    Node *find(const Key &key, Node *ptr) {
        if (!ptr) return nullptr;
        int _ = cmp(key, ptr->key);
        if (_ < 0) return find(key, ptr->l);
        if (_ > 0) return find(key, ptr->r);
        return ptr;
    }

    T &find(const Key &key) {
        return find(key, root)->x;
    }

    Node *exist(const Key &key) {
        return find(key, root);
    }

    Node *insert(const Key &key, const T &x, Node *ptr) {
        if (!ptr) return new Node(key, x);
        int _ = cmp(key, ptr->key);
        if (_ < 0) ptr->l = insert(key, x, ptr->l);
        if (_ > 0) ptr->r = insert(key, x, ptr->r);
        if (_ == 0) throw DuplicateKeyError();

        if (!is_red(ptr->l) && is_red(ptr->r)) ptr = rotate_left(ptr);
        if (is_red(ptr->l) && is_red(ptr->l->l)) ptr = rotate_right(ptr);
        if (is_red(ptr->l) && is_red(ptr->r)) flip_colors(ptr);

        return ptr;
    }

    void insert(const Key &key, const T &x) {
        root = insert(key, x, root);
    }

    template<typename U>
    void traverse(U *func, Node *ptr) {
        if (!ptr) return;
        traverse(func, ptr->l);
        func(ptr);
        traverse(func, ptr->r);
    }

    template<typename U>
    void traverse(U *func) {
        traverse(func, root);
    }
};


LLRB<String, Vector<const char *>> llrb;
LLRB<int, String> cnt;

void print(LLRB<int, String>::Node *ptr) {
    auto rec = llrb.find(ptr->x);
    for (int i = 0; i < rec.siz; i++) printf("%s ", rec.data[i]);
    printf("\n");
    return;
}

int main() {
    int N;

    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        char *name = new char[1024], *email = new char[1024];
        scanf("%s%s", name, email);
        auto *ptr = llrb.exist(String(email));
        if (!ptr) {
            llrb.insert(String(email), Vector<const char *>(name));
            cnt.insert(i, String(email));
        } else {
            ptr->x.append(name);
        }
    }

    cnt.traverse(print);

    return 0;
}