POJ 2513、Trie树、并查集以及欧拉路径

• POJ 2513、Trie树、并查集以及欧拉路径

这道题做的时候，干的最sb的事就是断点打印的东西没删干净，结果导致一开始怎么交怎么WA，后来怎么交怎么AC。不过仍然有很困惑的地方，就是在CSDN blog中，他的Trie树第二维只有15，但是能过，就很奇怪，而且将其改到应该是正确的26，却Runtime Error。

主要是三个方面，Trie树、并查集和欧拉回路/路径。并查集用于检查是否为连通图，不是必须的，但是可以减少2/3的运行时间，用DFS也可以做，但是不能使用std::vector前向星来储存图，太慢了，应该用链表式的前向星。

Trie树

Trie树的作用是判断输入的颜色是否已经出现过，一开始用hash做，以为hash散列开来就不会用太多时间，事实证明是不行的。Trie树还可以用来根据单词前缀寻找单词或者统计，稍作修改即可。一开始一直使用参考的Trie树，直接开一个二维数组保存，也不知道为什么他用15都能过，26可能是因为开的数组太大。

/* Trie-Tree using 2d array */
struct Trie
{
    int node_cnt;
    int tree[N][26]; // 0 in tree means no child
    int has_color[N];
    Trie()
    {
        node_cnt = 0;
        std::memset(tree, 0, sizeof(tree));
        std::memset(has_color, 0, sizeof(has_color));
    }
    int index(char ch)
    {
        return ch - 'a';
    }
    void insert(char ch[])
    {
        int root = 0, len = strlen(ch), idx;
        for (int i = 0; i < len; ++i)
        {
            idx = index(ch[i]);
            if (!tree[root][idx])
                tree[root][idx] = ++node_cnt;
            root = tree[root][idx];
        }
        has_color[root] = ++color_cnt;
    }
    int find(char ch[])
    {
        int root = 0, len = strlen(ch), idx;
        for (int i = 0; i < len; ++i)
        {
            idx = index(ch[i]);
            if (!tree[root][idx])
                return 0; // not found
            root = tree[root][idx];
        }
        return has_color[root];
    }
    int find_or_insert(char ch[])
    {
        int root = 0, len = strlen(ch), idx;
        for (int i = 0; i < len; ++i)
        {
            idx = index(ch[i]);
            if (!tree[root][idx])
                tree[root][idx] = ++node_cnt;
            root = tree[root][idx];
        }
        if (!has_color[root])
            has_color[root] = ++color_cnt;
        return has_color[root];
    }
};

这样的存储方式，其实也是按需分配，但可能实际并没有这么多的节点，所以超内存了，参考另一篇博客，使用树状存储则没有问题，代码见下。

/* Trie-Tree using linked tree */
struct TrieNode
{
    bool is_color;
    int color_id;
    TrieNode *t[26];
    TrieNode()
    {
        is_color = false;
        memset(t, NULL, sizeof(t));
    }
};
struct Trie
{
    int node_cnt;
    int has_color[N];
    TrieNode *root;
    Trie()
    {
        root = new TrieNode();
        node_cnt = 0;
    }
    int index(char ch)
    {
        return ch - 'a';
    }
    int find_or_insert(char ch[])
    {
        TrieNode *cur = root;
        int len = strlen(ch), idx;
        for (int i = 0; i < len; ++i)
        {
            idx = index(ch[i]);
            if (!cur->t[idx])
                cur->t[idx] = new TrieNode();
            cur = cur->t[idx];
        }
        if (!cur->is_color)
        {
            cur->is_color = true;
            cur->color_id = ++color_cnt;
        }
        return cur->color_id;
    }
};

并查集

并查集（Union & Find）用于判断图的连通性，其通过建立树状结构来组织不同的集合，当我们想要判断两个节点是否在同一集合中，只要查找这两个节点的根节点是否为同一个就行了。我们先定义find操作，通过递归查找找到当前节点的根节点。

int parent[N];
void init()
{
    for (int i = 0; i < N; ++i)
        parent[i] = i; // 一开始自成一派
}
int find(int u)
{
    return parent[u] == u ? u : find(parent[u]);
}

比如我们现在有五个节点0 1 2 3 4，假设有union操作如下，经过union(0, 1); union(1, 2); union(3, 4)之后的树状结构应该是下图，对应数组1 2 2 4 4。

void union(int u, int v)
{
    parent[u] = v;
}

此时进行union(1, 3)，则数组会变成1 4 2 4 4，如下图

这样的连通性显然是不对的，因此union操作应该将两树的根节点接在一起，才能让这两个集合连通，对应数组1 2 4 4 4

void union(int u, int v)
{
    int root1 = find(u);
    int root2 = find(v);
    if (root1 != root2)
        parent[root1] = root2;
}

当然如果每次都沿着整个树查找，将会是非常低效的，因此我们在沿树查找的过程中，将一颗子树中所有的节点的父节点都指向根节点

int find(int u)
{
    return parent[u] == u ? u : parent[u] = find(parent[u]); // 这种骚操作我当然是想不到的
}

上文的union(1, 3)不能体现这个效果，所以我们换成union(0, 3)，执行find(0)后如下图，对应数组2 2 2 4 4

执行find(3)之后树不变，整个函数执行完后如下图，对应数组2 2 4 4 4

这个时候如果执行一遍find(0)，则重排会变成4 3 4 4 4，对应下图

欧拉回路/路径

解决了连通性的问题，那么要判断欧拉回路/路径，则非常简单，只要统计一下度数为奇数的节点个数就行了，如果为0或者2，则构成欧拉回路或路径。

完整代码

#include <cstdio>
#include <cstring>
const int N = 500005;
int color_cnt = 0;
struct TrieNode
{
    bool is_color;
    int color_id;
    TrieNode *t[26];
    TrieNode()
    {
        is_color = false;
        memset(t, NULL, sizeof(t));
    }
};
struct Trie
{
    int node_cnt;
    int has_color[N];
    TrieNode *root;
    Trie()
    {
        root = new TrieNode();
        node_cnt = 0;
    }
    int index(char ch)
    {
        return ch - 'a';
    }
    int find_or_insert(char ch[])
    {
        TrieNode *cur = root;
        int len = strlen(ch), idx;
        for (int i = 0; i < len; ++i)
        {
            idx = index(ch[i]);
            if (!cur->t[idx])
                cur->t[idx] = new TrieNode();
            cur = cur->t[idx];
        }
        if (!cur->is_color)
        {
            cur->is_color = true;
            cur->color_id = ++color_cnt;
        }
        return cur->color_id;
    }
};
int degree[N] = {0};
int origin[N];
int find_origin(int u)
{
    return origin[u] == u ? u : origin[u] = find_origin(origin[u]);
}
void connect(int u, int v)
{
    int o1 = find_origin(u);
    int o2 = find_origin(v);
    if (o1 != o2)
        origin[o1] = o2;
}
int main()
{
    char aa[20], bb[20];
    Trie *t = new Trie();
    for (int i = 0; i < N; ++i)
        origin[i] = i;
    while (scanf("%s %s", aa, bb) != EOF)
    {
        int pa = t->find_or_insert(aa);
        int pb = t->find_or_insert(bb);
        connect(pa, pb);
        ++degree[pa];
        ++degree[pb];
    }
    bool is_connected = true;
    int source = -1;
    for (int i = 1; is_connected && i <= color_cnt; ++i)
    {
        if (source == -1)
            source = find_origin(i);
        else if (find_origin(i) != find_origin(source))
            is_connected = false;
    }
    int degree_cnt = 0;
    for (int i = 1; i <= color_cnt; ++i)
    {
        if (degree[i] & 1)
            ++degree_cnt;
    }
    if (degree_cnt <= 2 && is_connected)
        printf("Possible\n");
    else
        printf("Impossible\n");
}